2000年前的古希腊数学家埃拉特斯特尼创造了一种筛法,可以求得给定一个自然数以内的所有素数,只要在2—n内筛去不大于的素数的倍数,剩下的就是素数。
若自然数n不能被不大于任何素数整除,则n是一个素数。
可以把上面的汉字内容等价转换成为英语字母表示:
(1)
其中 表示顺序素数2,3,5,....。≠0。
若,则n是一个素数。
我们可以把(1)式内容等价转换同余式组表示 :
(2)
由于(2)的模,,..., 两两互素,
根据孙子定理(中国剩余定理)知,对于给定的,,...,,(2)式在...范围内有唯一解。
范例
k=1时,,解得n=3,5,7。求得了(3,)区间的全部素数。
k=2时,,解得n=7,13,19; ,
解得n=5,11,17,23。
求得了(5,)区间的全部素数。
k=3时 |
|
|
|
|
|
31 |
7,37 |
13,43 |
19
|
|
11,41 |
17,47 |
23 |
29
|
|}求得了(7,)区间的全部素数。
仿此下去可以求得任意大的数以内的全部素数。并且一个不漏地求得。
对于所有可能的,,...,,(1)和(2)式在...范围内,
有()()()...()
个解。
- 参见《素数之恋》第100页德比希尔著
- 《谈谈素数表达式》【中等数学】1999年2期--吴振奎教授
- 《关于一个寻找素数方法的理论依据》【中等数学】2001年4期--陈志云教授
- 《从台尔曼公式谈起》【中等数学】2002年5期--王晓明教授。