Алгоритмизация и программирование

Решето Эратосфена
Эратосфен Киренский
(Eratosthenes, Ερατοσθδνη)
(ок. 275-194 до н.э.)
Новая версия – решето Аткина .
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Алгоритм:
начать с k = 2
«выколоть» все числа через k, начиная с 2·k
перейти к следующему «невыколотому» k
если k <= N , то перейти к шагу 2
напечатать все числа, оставшиеся «невыколотыми»
высокая скорость, количество операций
нужно хранить в памяти все числа от 1 до N
O((N·log N)·log log N )
2
3
k·k
k·k <= N

Решето Эратосфена
Задача. Вывести все простые числа от 2 до N.
Объявление переменных:
цел i, k, N = 100
логтаб A[2:N]
Сначала все невычеркнуты:
нц для i от 2 до N
A[i]:= да
кц
const N = 100;
var i, k: integer;
A: array[2..N]
of boolean;
for i:= 2 to N do
A[i]:= True;

Решето Эратосфена
Вычёркивание непростых:
k:= 2
нц пока k*k <= N
если A[k] то
i:= k*k
нц пока i <= N
A[i]:= нет
i:= i + k
кц
все
k:= k + 1
кц
k:= 2;
while k*k <= N do begin
if A[k] then begin
i:= k*k;
while i <= N do begin
A[i]:= False;
i:= i + k
end
end;
k:= k + 1
end;