|
寻找素数之路
|
| |
一 、素数的表达式
首先，我们对整数进行重新排列，进行观察：
0 1 2 3
1 4 5 6
2 7 8 9
3 10 11 12
4 13 14 15
。 16 17 18
。 。。。 。。。 。。。
n 3x+1 3x+2 3x+3 ， x={0,1,2,3,........n}
从上图可以看出，整数不仅可以用2n-1，和2n来表示，而且还可以用3x+1，3x+2，3x+3的形式来表示，现在我们就从这些数中来寻找素数：
首先，令x=0，则得到三个基本数， 1，2，3；
其次，第三列中，不论x取何值，都是合数，故没有素数；
第三，令第一列中的x为偶数，令第二列中的x为奇数，这样就剩下下面两组奇数，
7 5
13 11
19 23
。。。 。。。
6n+7 6n+5 n={0,1，2，3，4，5，6。。。。}
除三个基本数， 1，2，3外；这两组奇数在整数中占的比例为：
（1/3）*（1/2）+（1/3）*（1/2）=1/3；
只有三分之一，这样，我们用试除法筛选素数时，时间将会大大缩短。同时，我们可以看出这两组数分别是差为6的等差数列，即
{5，11，17。。。6n+5}，n={0,1,2,3,...};
|
|
|
|
|
教育论文中心