Алгоритм
Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:
Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
Пусть переменная p изначально равна двум — первому простому числу.
Считая от p шагами по p, зачеркнуть в списке все числа от 2p до n кратные p (то есть числа 2p, 3p, 4p, …)
Найти первое не зачеркнутое число, большее чем p, и присвоить значению переменной p это число.
Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n
Теперь все не зачеркнутые числа в списке — простые.
На практике, алгоритм можно несколько улучшить следующим образом. На шаге № 3, числа можно зачеркивать, начиная сразу с числа p2, потому что все составные числа меньше его уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p2 станет больше, чем n.
Можно показать, что сложность алгоритма составляет O(nlog log n) операций в модели вычислений RAM, или O(n(log n)(log log n)) битовых операций, при условии вычисления и зачеркивания каждого кратного числа за время O(1), например при использования массивов с прямым доступом.
http://upload.wikime...ratosthenes.gif
Программный код
var b:array[2..100000] of boolean; i,j,n:longint; begin readln(n); for i:=2 to n do b[i]:= true; i:=2; while i*i<= n do begin if b[i]= true then begin j:=i*i; while j<=n do begin b[j]:=false; j:=j+i; end; end; if i=2 then i:=3 else i:=i+2; end; for i:=2 to n do if b[i] then write(i,' '); end.