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