实现功能:如题,筛出1——N内的所有素数
原理:如phile神犇所言,这次的才算是真正意义上的线性筛素数,其精髓在于if (i mod a[j])=0 then break;
因为——如果眼下的a[j]已经是i的因数了,则意味着即使再进行b[i*a[j]]:=1,那么I*b[j]也必然会被其他的数以同样的操作覆盖到,所以可以退出了,这个算法的思想在于减少重复劳动(鸣谢qcgrxx神犇,源链接)
1 var
2 i,j,k,l,m,n:longint;
3 a,b:array[0..1000000] of longint;
4 begin
5 readln(n);b[1]:=1;b[0]:=1;
6 for i:=2 to n do
7 begin
8 if b[i]=0 then
9 begin
10 inc(m);
11 a[m]:=i;
12 end;
13 for j:=1 to m do
14 begin
15 if a[j]>(n div i) then break;
16 b[a[j]*i]:=1;
17 if (i mod a[j])=0 then break;
18 end;
19 end;
20 while true do
21 begin
22 readln(m);
23 writeln(b[m]=0);
24 end;
25 end.