Искать здесь

в заметках в файлах в ссылках

Известен алгоритм, решето Эратосфена (по другим сведениям - Евклида), который позволяет вычислить таблицу, указывающую, какие числа в интервале от 1 до N являются простыми, а какие - составными. Существенным его недостатком является потребность в наличии своего элемента массива для каждого из чисел в интервале [1,N]. Такое расточительство оправдано лишь в том случае, когда требуется многократное и быстрое определение "простоты" различных чисел.

Рассмотрим алгоритм, требующий гораздо меньше памяти, причём "дойдем" до него в несколько шагов, путём последовательного улучшения.

Первый алгоритм, приходящий в голову примерно таков. Каждое число из интервала проверить на "простоту" по определению: оно должно делиться только на 1 и себя; подсчитаем сколько раз оно делится нацело и получим ответ:

For I:=1 to N do
begin
K:=0;
For J:=1 to I do
If (I/J)>trunc(I/J) then
K:=K+1;
If K=2 then
Writeln(I); {в случае только двух делителей}
end;

Рассмотрим недостатки данного алгоритма и последовательно исправим их.

Если нас интересует деление целого числа на целое, а точнее - остаток от него, то и следует использовать операции целочисленного деления div и mod. На Pascal по некоторым причинам результат компиляции Inc(K), работает быстрее, чем K:=K+1. Нет смысла делить i на все числа, большие, чем половина i - все равно нацело не разделится. Кроме того, подсчёт количества делений сам по себе не нужен: любое удачное деление нацело на число, не равное 1 и самому себе свидетельствует о том, что число не является простым. Следовательно, использование цикла For не является рациональным. Кроме того, делить на 1 и на само число также нет смысла.

For I:= 1 to N do
begin
J:=2;
K:=I div 2;
While (I mod J <> 0) and (J < K)
Do inc(J);
If J=K then
Writeln (I, ' простое число');
end;

Переменная K введена для того, чтобы выражение, которому она равна (а оно не меняется на протяжении каждого прохода тела внешнего цикла) не вычислялось каждый раз.

Дальнейшее улучшение алгоритма вычисления множества простых чисел (с точки зрения автора) возможно лишь за счет дополнительных затрат памяти. С другой стороны, любое подобного рода вычисление должно иметь своей целью построение таблицы простых чисел, так что излишество затрат памяти весьма сомнительно. Суть заключается в следующем: нет необходимости производить деления на составные числа, так как каждое составное число есть произведение простых его составляющих.

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

И, наконец, последнее ускорение алгоритма возможно при использовании для хранения таблицы простых чисел разреженного массива, в котором на месте простых чисел стоят, собственно, простые числа, а на всех остальных местах - 0. При этом размерность массива - N, но от деления можно отказаться. В итоге мы придём к алгоритму трёхтысячелетнего возраста - решету Эратосфена.