素数判断算法.doc

素数判断算法.doc判断素数
一个数n如果是合数，那么它的所有的因子不超过sqrt(n)— n的开方，那么我们可 以用这个性质用最直观的方法 来求出小于等于n的所有的素数。
num = 0;
for (i=2; i<=n; i++)
{ for (j=2; j<=sqrt (i); j++)
if( j%i=0 ) break;
if ( j>sqrt (i) ) pr ime[num++] = i; //这个 pr ime[]是 int 型，跟下
面讲的不同。
1
这就是最一般的求解n以内素数的算法。复杂度是o(n*sqrt (n))。
但我不认为这是算法。
根据定狡来进行判定，无法体现出算法的魅力！坯然如此，喜欢算法那就用优美的算法 来解决这个问題。
首先，介绍一下求广n范国内的素数的弼选法：
素数筛选法，也称“埃拉托色尼(Eratosthenes)弭法”，埃拉托色尼是古唏■腊著名的数 学家(膜幷一下)。素数歸选法操作如下，首先从2幵始，将2+k (k=1, 2, 3,・・・・・•n-2) 都对2进行整除运算，若(2+k)能整出2,说明这个数一定是合数，那就将它筛掉：然后 找下一个没有秋筛选掉的数字开始，就是从3开始，制下的数字对3进行整除运算，如果某 一个数能整除3,则将其卿料，接下来，按照这个模式一直那选，直至n做除數。
用表格表示一下筛选过程(广30):
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,用2卿选(红色的就是被筛扌卓的数字):
1
2
3
1 5
6
「7
8
9
10
11
12 n
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2,用下一个没有被没有被筛选掉的数字筛选:
1
2
3
4 nr 5
6 n
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
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除外)。
这个算法相比于用定义判斷素数要快很多倍。 用数学来解释：
n (n>1)的因子，小于等于
如果n为合数，那n的所有因子中一定存在素数因子，素数因子也满足小于等 于JA:如果n为素数，那n的因子只有1和它本身(定狡)。前一部分可以用 反证法证明，在这不再赘述。
接着，我们对这个算法进行优化：
在拜选的时候，我们发现，按照上面的流程，同一个素數数会被许多个素数进行判断， 而实际上，，2的筛选是从4开始的，凡是大于2且为2的倍数的数字都 被筛选掉了，3是从9开始筛选的，凡是剰下的大于3