關(guān)于怎么判斷一個(gè)數(shù) n 是否是質(zhì)數(shù)矾克，最簡(jiǎn)單的方法是枚舉 2 到 n?1，判斷是否是 n 的約數(shù)憔足。如果是胁附， n 肯定不是一個(gè)質(zhì)數(shù)酒繁。再仔細(xì)想想，如果 a 是 n 的一個(gè)約數(shù)控妻，那么必然有一個(gè)b 滿足 ab = n州袒，a≤√?n??? 和 b≤√?n??? 中必然有一個(gè)成立，因?yàn)槿绻鸻>√?n??? 并且 b>√?n???弓候，那么 ab>n郎哭，和 ab = n 矛盾。因此如果 n 是一個(gè)合數(shù)菇存，那么我們只需要枚舉到 √?n??? 就一定能找到 n的一個(gè)約數(shù)夸研。否則，n 肯定是一個(gè)質(zhì)數(shù)撰筷。下面是代碼：
int is_prime(int n)
{
for(int i = 2; i * i <= m; i++)
if(n % i == 0)
return 0;//不是質(zhì)數(shù)
return 1;//是質(zhì)數(shù)
}
更多的時(shí)候陈惰，需要預(yù)處理出一段區(qū)間上的質(zhì)數(shù)，如果按照之前的方法一個(gè)一個(gè)判斷毕籽，時(shí)間上肯定會(huì)承受不了抬闯。于是提出了一種預(yù)處理 1 到 N 上質(zhì)數(shù)的算法，稱(chēng)為 Eratosthenes 篩選关筒。
素?cái)?shù)篩選算法的基本思想是我們先假設(shè) 2 到 N 所有數(shù)都是素?cái)?shù)溶握。我們從 2 開(kāi)始掃描，對(duì)于一個(gè)數(shù) i蒸播，可以得到 2i, 3i ……ki 都不是素?cái)?shù)睡榆，因?yàn)檫@些數(shù)都有 i 這個(gè)因子，表示這些數(shù)不是素?cái)?shù)袍榆，一直枚舉到 N胀屿。對(duì)于每一個(gè)合數(shù)，它至少會(huì)被它的一個(gè)因子枚舉到包雀，所以可能證明這個(gè)算法的正確性宿崭。接下來(lái)分析時(shí)間復(fù)雜度，對(duì)于每個(gè) i才写，枚舉的次數(shù)為 n / i??葡兑，所以總時(shí)間復(fù)雜度為 N/2 + N/3 + … + N/N = O(NlgN) 。
下面是代碼:
for(int i = 2; i <= n; i++)
{
is_prime[i] = 1;
}
for(int i = 2; i <= n; i++)
{
for(int j = i * 2; j <= n; j += i)
{
is_prime[j] = 0;
}
}
上面的代碼便篩選出來(lái)了 n 以?xún)?nèi)的素?cái)?shù)赞草，如果 is_prime[i] = 1讹堤，i 是素?cái)?shù)，否則 i 是合數(shù)厨疙。上面的代碼還可以?xún)?yōu)化洲守。第一是基于每個(gè)合數(shù)必然有一個(gè)質(zhì)因子，所以我們可以只用質(zhì)數(shù)來(lái)篩選，第二是 j 的初始條件可以寫(xiě)成 j = i * i岖沛，因?yàn)楸热?j = i * k( k < i), 那么 j 肯定被k 篩選掉了暑始。第三是可以只用√?n??? 之前的質(zhì)數(shù)去篩選。優(yōu)化之后的時(shí)間復(fù)雜度比O(NlgN)還要低得多婴削。優(yōu)化以后的代碼如下：
for(int i = 2; i <= n; i++)
{
is_prime[i] = 1;
}
for(int i = 2; i * i <= n; i++)
{
if(is_prime[i])
{
for(int j = i * i; j <= n; j += i)
{
is_prime[j] = 0;
}
}
}
