O(n)线性筛选n以内的素数

O(n)线性筛选n以内的素数

（1）对于任何一个素数p，都不可能表示为两个数的乘积

（2）对于任何一个合数m = p₁^a1p₂^a2…p_m^am,这里p₁< p₂ < … <p_m，都能使用p₁^a1-1p₂^a2…p_m^am* p₁进行筛选

fillchar(prime,sizeof(prime),1);
prime[1]:=false;
fillchar(p,sizeof(p),0);
total:=0;
for i:=2 to n do
  begin
    if prime[i] then begin inc(total);p[total]:=i;end;
    for j:=1 to total do
      begin
        if p[j]*i>n then break;
        prime[p[j]*i]:=false;
        if i mod p[j]=0 then break;
      end;
  end;
for i:=1 to total do   writeln(p[i]);

 以下为略过偶数的线性筛选，速度还能提高一半。