当前位置:首页>维修大全>综合>

100以内的质数筛选法(判断质数的最快方法100以内)

100以内的质数筛选法(判断质数的最快方法100以内)

更新时间:2024-09-05 08:13:31

100以内的质数筛选法

先把100以内的数列出来,先除去1,1不是质数。然后用每个数字除以2,能整除的全部去掉;

将被除数单拿出来(质数)剩下的数再分别除以3,能整除的也全部去掉;这时剩下的数最小的是5,在将剩下的数除以5,能整除的去掉;然后是7…从小到大依次除一遍,如此下去直到所有的数都被筛完,这样筛选不会落下一个质数。

基本思想是:把从1开始的、某一范围内的正整数从小到大顺序排列,把不是素数的数全部赋值为0,最后只输出不是零的数即素数。1不是素数,首先把它换为0。剩下的数中选择最小的数是素数,然后把它的倍数全部换为0。依次类推,直到结束。

如有:

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

1不是素数,换为0。剩下的数中2最小,是素数,然后把它的倍数全部换为0,余下的数是:

0 2 3 0 5 0 7 0 9 0

11 0 13 0 15 0 17 0 19 0

21 0 23 0 25 0 27 0 29 0

剩下的数中3最小,是素数,然后把它的倍数全部换为0,如此下去直到所有的数都被筛完,求出的素数为:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

更多栏目