Простые числа

[Хыиуду]

Продолжаю собирать "кирпичики" для ветки "Решение типовых задач", если ее AiK все-таки откроет. Функция, определяющая, является ли число простым. Простейший вариант, далеко не самый быстрый, но наиболее понятный и вполне подходящий для небольших чисел (в районе до 10К-100К)

Код: Выделить всё

function issimple(x:longint):boolean;
  var i:longint;
begin
  for i:=2 to trunc(sqrt(x)) do
    if x mod i=0 then begin
       issimple:=false;exit; end;
    issimple:=true;
end;

[BBB]

Хыиуду,
можно значительно сократить количество проходов по циклу, если заменить верхний предел цикла с x div 2 на Trunc (sqrt (x)):

Код: Выделить всё

function issimple (x:longint):boolean;
  var i:longint;
begin
 { Особый случай: число 1 не относится к простым. }
 { Как, впрочем, не относится и к составным. }
  if (x = 1) then begin
    issimple := false;
    exit;
  end;

  for i:=2 to Trunc (sqrt (x)) do
    if x mod i=0 then begin
       issimple:=false;exit; end;

  issimple:=true;
end;

Ведь, если существует число V, бОльшее, чем Sqrt (X) и являющееся делителем числа X,
то тогда частное (целое число!) W=X/V:

W=X/V [заменяем знаменатель дроби на мЕньшее число, дробь от этого увеличивается] < X/(sqrt(X)) = sqrt(X)

То есть, W, которое также делитель числа X (т.к. X/W = V) меньше sqrt(X).

Таким образом, если число X имеет делитель, бОльший, чем sqrt(X), то оно также обязательно будет иметь делитель, мЕньший, чем sqrt(X).
Следовательно, искать делители (для установления самогО факта, простое число X или нет) достаточно в диапазоне от 2 до sqrt (X).

[Хыиуду]

Полностью согласен. Впрочем, для определения простоты одного небольшого числа это не сильно существенно.

[Хыиуду]

Только что заметил: это же Паскаль! int приводит к целому числу, но в формате extended, стало быть, для цикла это использовать нельзя. Поменял на trunc. Итого строка с циклом:
i:=2 to trunc(sqrt(x)) do