用筛选法计算 10000 以内的质数表
筛选法是一种古老的求不超过自然数 N(N>1)的所有质数的方法。把自然数1~N排列起来。最小的质数是 2,所以先把 1 划去,从 2 开始,把 2 留下,而把 2 后面所有能被 2 整除的数都划去。然后 2 后面第一个没划去的数是 3,把 3 留下,再把 3 后面所有能被 3 整除的数都划去。3 后面第一个没划去的数是 5,把 5 留下,再把 5 后面所有能被 5 整除的数都划去。这样一直做下去,每次筛选之后,下一个相邻的数都必然是质数,这样最后就会把不超过 N 的全部合数都筛掉,留下的就是不超过 N 的全部质数。
创建一个从 1 到 10000 的序列,把 1 划掉,从最小的质数 2 开始循环,将序列中当前数的倍数赋值为 0,保留当前数本身。这样,下一个不为0的数,不会是比它小的所有数的倍数,那它就是下一个质数。最后序列中不等于 0 的数即为 10000 以内的全部质数。
A |
B |
C |
|
1 |
10000 |
||
2 |
=to(A1) |
>A2(1)=0 |
|
3 |
for A2 |
if A3>0 |
=A1.step(A3,A3).to(2,) |
4 |
>A2(C3)=0 |
||
5 |
=A2.select(~>0) |
http://try.scudata.com.cn/try.jsp?splx=ExA001sxfqzsb.splx
A2生成1~10000的序列,并在B2将第一个成员赋值为0。
A3循环A2中的每个成员,B3判断当前成员是否大于0,如果是则说明是当前需要处理的质数,C3用step函数找到它的所有倍数的位置序列,并用to(2,)取出从第2个起的位置。C4将A2序列中这些位置的成员均赋值为0。
SPL可以用简单的语句处理集合,像A2中的to(A1),C3中的A1.step(A3,A3)都会返回集合。C4也可以针对集合做批量赋值。
循环完成后,A5取出序列中大于0的成员,即为质数列表:
熟练之后,也可以直接用循环函数写出来:
A |
|
1 |
10000 |
2 |
=to(A1).modify(1,0) |
3 |
>A2.run(if(~>0,A2(A1.step(~,~*2))=0)) |
4 |
=A2.select(~>0) |
http://try.scudata.com.cn/try.jsp?splx=ExA001sxfqzsb2.splx
A2用modify函数将序列的第一个成员改为0,效果和前一种方法中第二行的处理相同。
A3用循环函数,在A2中循环计算,对于非零的质数成员,将其后的倍数位置置0。
循环函数可以用一个函数实现循环计算,不必使用for循环中的代码块,代码更简洁。而SPL的函数可以嵌套使用,step函数作为参数,找到位置后做批量赋值。
英文版