筛选法求质数表

阅读(1029) 标签: 筛选, 质数表, 循环, step, for, if,

l  问题

筛选法是一种古老的求不超过自然数NN1)的所有质数的一种方法。具体做法是:先把N个自然数按次序排列起来。最小的质数是2,所以先把1划去,从2开始,把2留下,而把2后面所有能被2整除的数都划去。然后2后面第一个没划去的数是3,把3留下,再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5,把5留下,再把5后面所有能被5整除的数都划去。这样一直做下去,每次筛选之后,下一个相邻的数字都必然是质数,这样最后就会把不超过N的全部合数都筛掉,留下的就是不超过N的全部质数。

请在集算器中编写代码用这个算法找出10000以内的全部质数。 

l  思路

大致思路:声明一个从110000的有序序列,把1划掉,从最小的质数2开始循环,将序列中能够被当前数整除的数赋值为0,保留当前数本身,最后序列中不等于0的数即为10000以内的全部质数。

1.  定义110000的递增序列。

2.  将序列中值为1的成员赋值为0

3.  对递增序列从2开始循环,循环体中将序列中能够被当前循环数整除的数赋值为0

4.  剩下的不为0的数就是质数。

l  代码

 

A

B

C

 

1

10000

 

 

 

2

=to(A1)

 

 

生成从110000的序列

3

>A2(1)=0

 

 

将值为1的成员赋值为0

4

for A2

if A4>0

 

循环A2序列,如当前数不为0,则说明是质数,把其后能被该数整除的数都置为0

5

 

 

=A1.step(A4,A4).to(2,)

 

6

 

 

>A2(C5)=0

 

7

=A2.select(~>0)

 

 

最后剩下的不为0的数就是质数

 

l  结果