用筛选法计算 10000 以内的质数表

筛选法是一种古老的求不超过自然数 NN1)的所有质数的方法。把自然数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,如果是则说明是当前需要处理的质数,C3step函数找到它的所有倍数的位置序列,并用to(2,)取出从第2个起的位置。C4A2序列中这些位置的成员均赋值为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

A2modify函数将序列的第一个成员改为0,效果和前一种方法中第二行的处理相同。

A3用循环函数,在A2中循环计算,对于非零的质数成员,将其后的倍数位置置0

循环函数可以用一个函数实现循环计算,不必使用for循环中的代码块,代码更简洁。而SPL的函数可以嵌套使用,step函数作为参数,找到位置后做批量赋值。