前言
今天做ACM的時候，遇到了素數(shù)的檢測，檢測一個范圍內的素數(shù)的時候，如果用最簡單的那種方法，超時嚴重，因此學習了一個新的素數(shù)檢測算法——素數(shù)篩選法，這里也是跟大家分享一下
素數(shù)
素數(shù)的定義
一個大于1的整數(shù)，如果不能被除1和它本身之外的其它正整數(shù)整除，則是素數(shù)（又稱質數(shù)）
合數(shù)的定義
一個大于1的整數(shù)，如果不是素數(shù)則是合數(shù)。其中能整除這個數(shù)的正整數(shù)叫做約數(shù)，不等于1也不等于合數(shù)本身的約數(shù)叫做非平凡約數(shù)。
注意：
1既不是素數(shù)也不是合數(shù)
檢測素數(shù)
所謂素數(shù)檢測，就是給定任意一個大于1的整數(shù)，判斷這個整數(shù)是否為素數(shù)。
因子檢測法
方法：就是從2到ｎ-1一個個的拿來嘗試，看能否整除ｎ，如果存在能夠整數(shù)ｎ的（找到一個因子），則ｎ不是素數(shù)，否則認為ｎ是素數(shù)。實際，是不需要試探到ｎ-1的，只要的ｎ的二次方根即可，原因是：
設n = a * b,且a、b均為n非平凡約數(shù)，顯然a > n的二次方根和b > n的二次方根不可能同時成立，因為同時成立時 a * b就會大于n，所以如果n存在非平凡約數(shù)，至少有一個小于等于n的二次方根，因此只要遍歷到ｎ的二次方根即可。
因子檢測的實現(xiàn)代碼如下（ｃ）：
int isPrime(int n)
{
int i, flag;
flag = (n <= 1)? 0 : 1;
for(i = 2; i <= sqrt(n); i ++)
{
if(n % i == 0)
{
flag = 0;
break;
}
}
return flag;
}
測試結果：
時間復雜度：
很明顯，因子檢測算法的時間復雜度是0（ｎ的二次方根）,一般來說，這個時間復雜度已經很牛叉了，但是如果我要求ｎ以內所有的素數(shù)集合，那時間復雜度瞬間就到了n * n的二次方根，這個對于ｎ很大時是不可忍受的
素數(shù)篩選法
利用素數(shù)因子檢測法去超找ｎ以內的所有素數(shù)，時間復雜度太高，不可忍受，因此這里介紹另外一種算法，素數(shù)篩選法，可以大大的節(jié)省時間，帶來的直接功效是九度ａｃｍ關于素數(shù)檢測的題我瞬間ａｃ，用素數(shù)因子檢測基本都是ｗａ。
原理：
當i是素數(shù)的時候，則ｉ的所有倍數(shù)必然是合數(shù)。如果ｉ已經判斷不是素數(shù)了，那么找到ｉ后面的質數(shù)來把這個質樹的倍數(shù)篩掉。
求20以內素數(shù)的篩選過程：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
第一步，因為所有的偶數(shù)和0,1必然不是質數(shù)，則將這些數(shù)的對應的value標記為flase，其余為true。
第二步：
i = 3,由于prime[3] = 1,則prime[6],prime[9],prime[12],prime[15],prime[18]均標記為0;
i = 4,由于prime[4] = 0,則continue，不做處理;
i = 5 > sqrt(20),算法結束
時間復雜度：
這個時間復雜度由于我的數(shù)學知識有限，也沒法把計算過程解釋出來，總之確實是很快，至于為什么ｉ= 5就結束了，原因跟素數(shù)因子法里面的原理是一樣的，因為ｎ的因子必然有一個是小于等于n的二次方根的。
素數(shù)篩選法實現(xiàn)代碼：
void getPrimeArray(int *prime)
{
int i, j;
//初始化素數(shù)標識數(shù)組
for(i = 0; i < max; i ++)
{
if((i == 2 || i % 2 != 0) && i != 1)
{
prime[i] = 1;
} else
{
prime[i] = 0;
}
}
//進行素數(shù)的篩選
for(i = 2; i * i < max; i ++)
{
if(prime[i])
{
for(j = 2 * i; j < max; j += i)
{
prime[j] = 0;
}
}
}
}
參考資料
更多文章、技術交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
