O(n) 筛法求素数

var tot,i,j,k,m,n:longint;
prime:array[0..100000] of boolean;
p:array[0..100000] of longint;
begin
read(n);
fillchar(prime,sizeof(prime),true);
prime[1]:=false;
tot:=0;
fillchar(p,sizeof(p),0);
for i:=2 to n do
begin
if prime[i] then
begin
inc(tot);
p[tot]:=i;
end;
for j:=1 to tot do
begin
if i*p[j]>n then break;
prime[i*p[j]]:=false;
if i mod p[j]=0 then break;
end;
end;
for i:=1 to tot do
writeln(p[i]);
end.

O(n) 筛法求素数

原文：http://www.cnblogs.com/syzcannot/p/4057644.html