今天在面試時(shí)被問(wèn)到了一個(gè)問(wèn)題：求不大于n的最大素?cái)?shù)获三，當(dāng)時(shí)只想出暴力解法弄唧，回來(lái)查資料找到了正確的求解方法袜瞬。
素?cái)?shù)篩法是這樣的：
1. 開(kāi)一個(gè)大的bool型數(shù)組prime[]冲杀，大小就是n+1就可以了.先把所有的下標(biāo)為奇數(shù)的標(biāo)為true,下標(biāo)為偶數(shù)的標(biāo)為false.
vector<bool> prime(n+1, true);
for(int i=0; i<n+1; ++i)
if(i%2 == 0)
prime[i] = false;
- 然后：
for(int i=3; i<=sqrt(n); i+=2)
{ if(prime[i])
for( j=i+i; j<=n; j+=i ) prime[j]=false;
}
3.最后輸出bool數(shù)組中的值為true的單元的下標(biāo)效床，就是所求的n以?xún)?nèi)的素?cái)?shù)了。
背后的原理是：當(dāng)i是素?cái)?shù)的時(shí)候权谁，i的所有的倍數(shù)必然是合數(shù)剩檀。如果i已經(jīng)被判斷不是質(zhì)數(shù)了，那么再找到i后面的質(zhì)數(shù)來(lái)把這個(gè)質(zhì)
數(shù)的倍數(shù)篩掉旺芽。
