算法模板——线性筛素数
实现功能：如题，筛出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.本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-05-08 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读