数学建模社区-数学中国

标题: 一种不用判断素数筛选素数的方法 [打印本页]

作者: tysh670407    时间: 2016-7-5 17:46
标题: 一种不用判断素数筛选素数的方法
一种不用判断素数筛选素数的方法
田永胜
(内蒙古自治区 吉兰泰 750333
摘要:本文给出了一种不用判断素数筛选素数的方法及特点。
关键词: 判断素数;筛选素数;数列;互乘
中图分类号:O156.1
现在人们使用的筛法,是由古希腊数学家埃拉托色尼所提出的一种简单检定素数的方法。要筛出小于n的素数,先找出√n以内的素数。然后用√n以内的素数,去筛√nn的素数。
这种方法对于n位数较小的情况来说,比如210位数字,比较容易,对于数字位数较大的情况,比如20100位,则比较费时。那么,有没有一种方法不用判断素数就可以筛选素数呢?下面,我们就进行这方面的研究。
因为1既不是素数,也不是合数,不做研究,剩余的自然数从2开始进行排列,一直到9,共8个数列,如表1所示:
n
8n+2
8n+3
8n+4
8n+5
8n+6
8n+7
8n+8
8n+9
0
2
3
4
5
6
7
8
9
1
10
11
12
13
14
15
16
17
2
18
19
20
21
22
23
24
25
3
26
27
28
29
30
31
32
33
4
34
35
36
37
38
39
40
41
5
42
43
44
45
46
47
48
49
6
50
51
52
53
54
55
56
57
7
58
59
60
61
62
63
64
65
8
66
67
68
69
70
71
72
73
9
74
75
76
77
78
79
80
81
1 自然数排列表
从表1可以看出数列8n+28n+48n+68n+8,均为偶数列,数列8n+38n+58n+78n+9,均为奇数列,而素数就在分布这4个数列上。
我们先看这四个奇数列上的数有什么特点:
首先,把四个奇数列上的数互乘或自乘,
3×9=27,除83,在数列8n+3上,同样,5×7=35,除83,也在数列8n+3上;
3×7=21,除85,在数列8n+5上,同样,5×9=45,除85,也在数列8n+5上;
3×5=15,除87,在数列8n+7上,同样,7×9=3,除87,也在数列8n+7上;
3×3=9,除81,在数列8n+9上,同样,5×5=25,除81,在数列8n+9上;7×7=49,除81,在数列8n+9上,同样,9×9=81,除81,也在数列8n+9上;
四个奇数列上的数互乘或自乘与筛选素数有什么关系呢?
我们先拿数列上的几个数来研究一下,例如n[0,:
在数列8n+3上,当n=012345时,数列为31119273543。当xy0时,(8x+3)和(8y+9)的乘积27和(8x+5)和(8y+7)的乘积35,也在这个数列上,筛去这两个数,剩余的就是素数3111943
在数列8n+5上,当n=012345时,数列为51321293745,当xy0时,(8x+3)和(8y+7)的乘积21和(8x+5)和(8y+9)的乘积45,也在这个数列上,筛去这两个数,剩余的就是素数5132937
在数列8n+7上,当n=012345时,数列为71523313947,当xy0时,(8x+3)和(8y+5)的乘积1539,也在这个数列上,筛去这两个数,剩余的就是素数7233147
在数列8n+9上,当n=012345时,数列为91725334149,当xy0时,(8x+3)和(8y+3)的乘积933,(8x+5)和(8y+5)的乘积25,(8x+7)和(8y+7)的乘积49,也在这个数列上,筛去这4个数,剩余的就是素数1741
经过研究发现,数列(8n+3)与数列(8n+9)上的数相乘及数列(8x+5)与数列(8y+7)上的数相乘都在数列(8n+3)上,只要筛去(8x+3)(8y+9)和(8x+5)(8y+7)这些数,剩余的数都是素数。(nxy=0123…
同理,在数列8n+5上,只要筛去(8x+3)(8y+7)和(8x+5)(8y+9)这些数,剩余的数都是素数。(nxy=0123…
同理,在数列8n+7上,只要筛去(8x+3)(8y+5)和(8x+7)(8y+9)这些数,剩余的数都是素数。(nxy=0123…
同理,在数列8n+9上,只要筛去(8x+3)(8y+3)和(8x+5)(8y+5)(8x+7)(8y+7)和(8x+9)(8y+9)这些数,剩余的数都是素数。(nxy=0123…
上述筛法中,只要筛掉数列中的合数,剩余的就是素数,而这些合数是这4个奇数列的互乘或自乘,不需要去判断一个数是不是素数,因此比埃拉托色尼筛法快很多。
这种筛法既可以筛选2到某一个数n之间的素数,也可以筛选某一区间内的素数,比如在数列8n+7上,寻找 n1030之间的素数,只需筛去满足不等式
247≥(8x+3)(8y+5)≥87247≥(8x+7)(8y+9)≥87  
上的数即可(筛选过程会有满足条件的重复数出现,计数时只记1次),剩余的大于87,小于247的数就是素数。
在数列8n+7上,n[10,时的值为8795103111119127135143151159167175183191199207215223231239247
满足不等式 247≥(8x+3)(8y+5)≥87 的数有8795111135143159183207215231247
满足不等式 247≥(8x+7)(8y+9)≥87 的数有 119135175231
剩余的数 103127151191199223239 就是素数。
这种方法可以计算出数列在某个区间的素数个数。即将区间的数字个数减去满足不等式的个数,余数就是素数个数。
上面研究的是8个数列排列的情况(8n+29),也可以推广到16个数列排列的情况(16n+217),32个数列排列的情况(32n+233),以及64列,128列,256列,512列,1024……等等。
这种方法既可以用于筛选素数,也可以用于分解合数。既可以用于筛选某一个数列上的所有素数,也可以筛选数列上某一区间的素数。

' @+ o5 z' y. v( ^
作者: tysh670407    时间: 2016-7-11 17:29
请会编程的网友测试一下,看这种方法对不对。
: L$ j( O1 y2 ]% A" T
作者: 武汉方程    时间: 2016-11-20 20:42
学习了,很新颖。谢谢。
0 i/ z& p/ v0 g. l8 s. B




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5