Функция определения простоты числа, оценка двух алгоритмов

@MB_worst · Регистрация: 27.01.2013

Author24 — интернет-сервис помощи студентам

Приветствую, очень нужна помощь.
В общем даны 2 функции определения, одна с Break, вторая с Exit.

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
function IsSimple n: Integer): Boolean;
  var
    i: Integer;
  begin
    IsSimple:=True;
    for i:=2 to Trunc(Sqrt(n)) do
      if (n mod i)=0 then
      begin
        IsSimple:=False;
        Break
      end
  end;

Pascal
1
2
3
4
5
6
7
8
9
10
function simple(N: integer): boolean;
begin
  Result := True;
  for var i:=2 to round(sqrt(N)) do 
    if N mod i = 0 then
    begin
      Result := False;
      exit;
    end;
end;

Обе правильные, как работают алгоритмы я представляю, что из себя представляют Break и Exit я тоже знаю. Но вопрос в том, какой из алгоритмов эффективнее, чтобы его можно было использовать в дальнейшем?
В большинстве пособий мало что сказано о Break и Exit, в основном пишется, что это "не структурно, спагетти блаблабла", в школе тоже спросить не у кого, в математических оценках алгоритмов не шарю, пожалуйста, помогите.

@Cyborg Drone · 28.03.2013, 00:40

Код написан с ошибками, ну да ладно.

Break - досрочный выход из цикла.

Exit - досрочное завершение процедуры, функции или программы и передача управления вызывающей программе.

У меня есть подозрение, что Вы не различаете понятий "алгоритм" и "реализация алгоритма". Алгоритм в обеих функциях используется один и тот же.

В первом фрагменте кода происходит выход из цикла, затем выход из функции.
Во втором фрагменте кода выход из функции происходит прямо из цикла. Как бы эффективнее, но, вообще, не быстрее.
Вот и вся разница. Вернее, безразница.

Чем здесь округлять, Trunc или Round, всё равно, но Trunc вроде как быстрее.

Всего Вам доброго.

@MB_worst · 28.03.2013, 01:19 **[ТС]**

Cyborg Drone Спасибо за ответ! По поводу ошибок, если я правильно понял, имеется вторая программа. Это не ошибки, а особенности pascalabc, просто решил писать в Turbo Pascal, ибо тут народу побольше. Еще раз спасибо

@Cyborg Drone · 28.03.2013, 01:25

Да нет же, в обеих фрагментах со скобками беда.

@MB_worst · 28.03.2013, 01:41 **[ТС]**

Ага, заметил) Ну тогда еще к Вам такой вопрос, по идее 1 не является простым числом, получается, что грамотнее будет добавить

Pascal
1
(if n mod i<>0) and (n=1) then begin simple:=false;

?

Добавлено через 1 минуту
А нет, написал не подумав

Добавлено через 2 минуты

Pascal
1
2
if (z mod i<>0) and (z<>1) then begin pros:=true;
exit

Вот так кажется правильнее

@Cyborg Drone · 28.03.2013, 03:10

Для n = 1 проверка бессмысленна: i > 2, и по-любому (n mod i) = 1.
Ой. Сразу не усмотрел. И с циклом беда при N < 4 (с Trunc) или при N < 3 (с Round).
Так, наверное, с учётом вышесказанного:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function simple(N: integer): boolean;
var i: integer;
begin
if n < 2 
  then Result := False
  else if n < 4 
    then Result := True
    else begin
      Result := True;
      for i:=2 to round(sqrt(N)) do 
        if N mod i = 0
          then begin
            Result := False;
            exit;
          end;
    end;
end;

Добавлено через 11 минут
Хотя... в большинстве диалектов pascal

Pascal
1
for i := 2 to 1 do

не выполнится ни разу... Всё ж так, наверное...

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function simple(N: integer): boolean;
var i: integer;
begin
if n < 2 //Мало ли, может, отрицательное число попадётся... 
         //Защита от дурака нужна. Заодно и с 1 разобрались.
  then Result := False
  else begin
    Result := True;
    for i:=2 to round(sqrt(N)) do 
    if N mod i = 0
      then begin
        Result := False;
        exit;
      end;
  end;
end;

@MB_worst · 28.03.2013, 11:54 **[ТС]**

Cyber Drone
А смысл? Или я чего-то не догоняю или отрицательные числа и так не будут проверяться, ибо в цикле со счетчиком программа не будет вычислять корень из отрицательного числа.
вот мой вариант

Pascal
1
2
3
4
5
6
7
8
9
10
var a:integer;
function simple (x:integer):boolean;
var i:integer;
begin
simple:=false;
for i:=2 to trunc(sqrt(x)) do
if (x mod i<>0) and (x<>1) then begin simple:=true;
exit
end;
end;

Добавлено через 10 минут
А, с циклом и правда беда, как-то не усмотрел. Ваш вариант грамотнее

@Cyborg Drone · 28.03.2013, 12:34

MB_worst, Вы не правы. Почему это не будет? Будет, будет... При вычислении границы цикла и возникнет ошибка. Вот если бы вторая граница не вычислялась, а сразу бы была < 0, тогда да. Может, в каком-то диалекте pascal и делается по-Вашему, не знаю. Но нужно предусматривать в том числе и то, что программа будет переводиться вообще на другие языки программирования. Это такое правило хорошего тона. Вот работа над ошибками:

Pascal
1
2
3
4
5
6
7
8
9
10
11
var a:integer; //лишняя строка
function simple (x:integer):boolean;
var i:integer;
begin
simple:=false; //true, а не false
for i:=2 to trunc(sqrt(x)) do //при x < 0 будет ошибка - sqrt(x) из отрицательного числа
if (x mod i<>0) and (x<>1) then begin simple:=true; //false, а не true
//лишнее условие x <> 1, и так при x < 4 выражение trunc(sqrt(x)) < 2 и for не выполнится.
exit
end;
end;

А с trunc, наверное, быстрее будет, меньше скрытых условий относительно round... Так что, полагаю, мой последний вариант, разве что round на trunc заменить...

Добавлено через 1 минуту

Не по теме:

Ой... Прозевал Ваше сообщение... Да и ладно, вроде всё равно всё в тему. Всего Вам доброго.

Добавлено через 4 минуты
Нет... Полагаю, чтобы с циклом разночтений не было, всё же мой предпоследний вариант, только с trunc.

@MB_worst · 28.03.2013, 12:47 **[ТС]**

Я понял, спасибо за ликбез. Удачи

Добавлено через 11 минут
В общем, наиболее оптимальный вариант вот этот

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function simple(N: integer): boolean;
var i: integer;
begin
if n < 2 
  then Result := False
  else begin
    Result := True;
    for i:=2 to trunc(sqrt(N)) do 
    if N mod i = 0
      then begin
        Result := False;
        exit;
      end;
  end;
end;

Я вывел первые 30 простых чисел, вроде работает правильно

Добавлено через 53 секунды
и никаких разногласий с циклом

@Cyborg Drone · 28.03.2013, 13:09

Сообщение от MB_worst

и никаких разногласий с циклом

Да, точно... Проверка на завершение цикла выполняется перед телом цикла, и по канонам языка для выполнения операторов в цикле нужно, чтобы переменная-счётчик была не больше конечного значения.

Добавлено через 52 секунды
Значит, всё же этот вариант.

@MB_worst · 28.03.2013, 22:43 **[ТС]**

Немного упростил

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
function simple(N: integer): boolean;
var i: integer;
begin
if n>1 then Result:=True;
 
    for i:=2 to trunc(sqrt(N)) do 
    if (N mod i = 0) 
      then begin
        Result := False;
        exit;
      
  end;
end;

Добавлено через 2 минуты
Немного упростил

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
function simple(N: integer): boolean;
var i: integer;
begin
if n>1 then Result:=True;
 
    for i:=2 to trunc(sqrt(N)) do 
    if (N mod i = 0) 
      then begin
        Result := False;
        exit;
      
  end;
end;ч

@Cyborg Drone · 31.03.2013, 14:21

Однако, зря. Появился ляпсус. Если n <= 1, чему будет равен Result? Ответ: неизвестно чему. Поскольку ни if, ни for не выполнятся, Result останется неиницилизированным. И что функция выдаст вожделенное false в этом случае - далеко не факт.

Новые блоги и статьи Все статьи Все блоги /
Что нового в C# 14 UnmanagedCoder 10.03.2025 Предстоящая версия C# 14 обещает принести изменения, которые сделают разработку еще более приятной и эффективной. Что стоит отметить, так это влияние сообщества разработчиков на формирование новых. . .	Формулы поворота Igor3D 10.03.2025 Добрый день Тема Эти формулы приводятся во множестве тьюториалов, часто под видом "матрица вращения на плоскости". x' = x * cos(a) - y * sin(a) y' = y * cos(a) + x * sin(a) Как бы Вы их. . .	Что нового в .NET 10 UnmanagedCoder 10.03.2025 . NET 10 выходит как релиз с длительной поддержкой (LTS), включающей три года обновлений. В этом обновлении Microsoft сфокусировались на нескольких направлениях: производительность, оптимизация. . .	Отложенное высвобождение, RCU и Hazard Pointer в C++26 NullReferenced 09.03.2025 Многопоточное программирование стало важной частью современной разработки. Когда несколько потоков одновременно работают с общими данными, возникает целый ряд проблем, связанных с синхронизацией и. . .	Неблокирующийся стек на C++26 NullReferenced 09.03.2025 Традиционные способы синхронизации в многопоточном программировании — мьютексы, семафоры, условные переменные — часто превращаются в узкое место в плане производительности. При этом неблокирующиеся. . .
Обработка строк в C++26: Новые возможности string и string_view NullReferenced 09.03.2025 Новый стандарт C++26 предлагает много улучшений для работы с привычными string и относительно новыми string_view. string_view - это невладеющая ссылка на последовательность символов, появившаяся в. . .	Мой первый аддон для Blender 3D, с помощью нейронки (не зная даже азов пайтона, но это не значит что так и с остальным). Hrethgir 09.03.2025 Потратил весь день. Пол-дня мне хватило, чтобы понять что с версией с 14B мне не одолеть написание функционального кода, на языке с которым я вообще никак не знаком - пайтон. Версия 22B от другого. . .	Einstein@Home сегодня исполняется двадцать лет! Programma_Boinc 09.03.2025 Einstein@Home сегодня исполняется двадцать лет! Отправлено 19 февраля 2025 года в 17:20:21 UTC Я хочу поздравить всех наших волонтеров, разработчиков и ученых из Einstein@Home. Мы официально. . .	Заполнители и расширенный набор символов в C++26 NullReferenced 09.03.2025 C++26 представляет два важных обновления: заполнители и расширенный набор символов. Заполнители (placeholders) решают давнюю проблему лаконичности кода в шаблонных выражениях и лямбда-функциях. Они. . .	Контракты в C++26 NullReferenced 09.03.2025 Контракты – это механизм, позволяющий указывать предусловия, постусловия и инварианты для функций в коде. Эта функциональность должна была стать частью C++20, но была исключена на встрече комитета. . .

@Cyborg Drone Модератор 10140 / 5476 / 3370 Регистрация: 17.08.2012 Сообщений: 16,730
	28.03.2013, 00:40	2
	Код написан с ошибками, ну да ладно. Break - досрочный выход из цикла. Exit - досрочное завершение процедуры, функции или программы и передача управления вызывающей программе. У меня есть подозрение, что Вы не различаете понятий "алгоритм" и "реализация алгоритма". Алгоритм в обеих функциях используется один и тот же. В первом фрагменте кода происходит выход из цикла, затем выход из функции. Во втором фрагменте кода выход из функции происходит прямо из цикла. Как бы эффективнее, но, вообще, не быстрее. Вот и вся разница. Вернее, безразница. Чем здесь округлять, Trunc или Round, всё равно, но Trunc вроде как быстрее. Всего Вам доброго. 1

@MB_worst 1 / 1 / 1 Регистрация: 27.01.2013 Сообщений: 8
	28.03.2013, 01:19 [ТС]	3
	Cyborg Drone Спасибо за ответ! По поводу ошибок, если я правильно понял, имеется вторая программа. Это не ошибки, а особенности pascalabc, просто решил писать в Turbo Pascal, ибо тут народу побольше. Еще раз спасибо 0

@Cyborg Drone Модератор 10140 / 5476 / 3370 Регистрация: 17.08.2012 Сообщений: 16,730
	28.03.2013, 01:25	4
	Да нет же, в обеих фрагментах со скобками беда. 0

@Cyborg Drone Модератор 10140 / 5476 / 3370 Регистрация: 17.08.2012 Сообщений: 16,730
	28.03.2013, 13:09	10
	Сообщение от MB_worst и никаких разногласий с циклом Да, точно... Проверка на завершение цикла выполняется *перед* телом цикла, и по канонам языка для выполнения операторов в цикле нужно, чтобы переменная-счётчик была *не больше* конечного значения. Добавлено через 52 секунды Значит, всё же этот вариант. 1

@Cyborg Drone Модератор 10140 / 5476 / 3370 Регистрация: 17.08.2012 Сообщений: 16,730
	31.03.2013, 14:21	12
	Однако, зря. Появился ляпсус. Если n <= 1, чему будет равен Result? Ответ: неизвестно чему. Поскольку ни if, ни for не выполнятся, Result останется неиницилизированным. И что функция выдаст вожделенное false в этом случае - далеко не факт. 0