|
轉(zhuǎn)載文章 ： 轉(zhuǎn)載自Tanky Woo 的程序人生 , <------- 請大家多多支持奮斗哥哈
The Sieve of Eratosthees
愛拉托遜斯篩選法思想：對于不超過n的每個非負(fù)整數(shù)P，刪除2*P, 3*P…，當(dāng)處理
完所有數(shù)之后，還沒有被刪除的就是素數(shù)。
若用vis==1表示已被刪除，則代碼如下：
—————————————————–
代碼一：
- memset(vis, 0, sizeof(vis));
- for(int i = 2; i <= 100; i++)
- for(int j = i*2; j <= 100; j += i)
- vis[j] = 1;
復(fù)制代碼
上面的代碼效率已經(jīng)很高了。
但還可以繼續(xù)優(yōu)化。
看一個改進(jìn)的代碼：
——————————————————
代碼二：
- int m = sqrt(double(n+0.5));
- for(int i = 2; i <= m; i++)
- if(!vis[i])
- {
- prime[c++] = i;
- for(int j = i*i; j <= n; j += i)
- {
- vis[j] = 1;
- }
- }
復(fù)制代碼
——————————————————
先分析代碼一：
這個代碼就是簡單的將Eratosthenes篩選法描述出來。不用多說。
分析代碼二：
考慮幾點：
1.為何從i=2~m?
因為下面的j是從i*i開始的。
2.為何j從i*i開始？
因為首先在i=2時，偶數(shù)都已經(jīng)被刪除了。
其次，“對于不超過n的每個非負(fù)整數(shù)P”， P可以限定為素數(shù)，
為什么？
因為，在 i 執(zhí)行到P時，P之前所有的數(shù)的倍數(shù)都已經(jīng)被刪除，若P
沒有被刪除，則P一定是素數(shù)。
而P的倍數(shù)中，只需看：
(p-4)*p, (p-2)*p, p*p, p*(p+2), p*(p+4)
（因為P為素數(shù)，所以為奇數(shù)，而偶數(shù)已被刪除，不需要考慮p*(p
-1)等）
又因為(p-4)*p 已在 (p-4)的p倍中被刪去，故只考慮：
p*p, p*(p+2)….即可
這也是i只需要從2到m的原因。
當(dāng)然，上面 p*p, p*(p+2)…的前提是偶數(shù)都已經(jīng)被刪去，而代碼
二若改成 j += 2*i ,則沒有除去所有偶數(shù)，所以要想直接 加2*i
。只需在代碼二中memset()后面加：
for(int i = 4; i <= n; i++)
if(i % 2 == 0)
vis = 1;
這樣，i只需從3開始，而j每次可以直接加 2*i.
——————————————————
這里用代碼二給大家一個完整的代碼：
- //版本二
- //Author: Tanky Woo
- //BBS:www.cppleyuan.com
- #include <stdio.h>
- #include <string.h>
- #include <math.h>
- int vis[100];
- int prime[100];
- int c = 0;
- int n;
- int main()
- {
- scanf("%d", &n);
- int cnt = 1;
- memset(vis, 0, sizeof(vis));
- int m = sqrt(double(n+0.5));
- for(int i = 2; i <= m; i++)
- if(!vis[i])
- {
- prime[c++] = i;
- for(int j = i*i; j <= n; j += i)
- {
- vis[j] = 1;
- //printf("%d\n", j);
- }
- }
- for(int i = 2; i < n; i++)
- {
- if(vis[i] == 0)
- {
- printf("%d ", i);
- cnt++;
- if(cnt % 10 == 0)
- printf("\n");
- }
- }
- printf("\ncnt = %d\n", cnt);
- return 0;
- }
復(fù)制代碼
完畢。
歡迎大家和我交流。
轉(zhuǎn)載文章 ： 轉(zhuǎn)載自Tanky Woo 的程序人生 |