質(zhì)數(shù)判斷
我們來看這么一道問題：
給定一個范圍N，你需要處理M個某數(shù)字是否為質(zhì)數(shù)的詢問（每個數(shù)字均在范圍1-N內(nèi)）N<=10000000叔壤，M<=100000
首先很容易聯(lián)想到使用枚舉法來確定題目的整體框架
for( i: 1~m)
{
cin>>x;
if(x是質(zhì)數(shù))
{
yes;
}else
{
no;
}
}
關鍵在于質(zhì)數(shù)判斷部分竹海。
質(zhì)數(shù)的判斷問題我們可以從定義出發(fā)昭伸。質(zhì)數(shù)缀拭，又稱素數(shù)织阳，是除了1和它自身以外沒有其他的因子眶蕉。
bool isPrime(int x)
{
if(x==1) return false;
for(int i=2;i<x;i++)
{
if(x%i==0) return false;
}
return true;
}
稍微計算下整體的時間復雜度砰粹，可以發(fā)現(xiàn)用時會比較多唧躲，那么我們可以思考下優(yōu)化的地方。整體框架確定后碱璃，能優(yōu)化的地方可從質(zhì)數(shù)判斷入手弄痹。思考，一個數(shù)去除以比它的一半還要大的數(shù)嵌器，一定是除不盡的肛真，因此，除到x/2就夠了爽航。
再改進一下蚓让，一個數(shù)若可以進行因數(shù)分解，那么分解得到的兩個數(shù)一個范圍小于sqrt(x),另一個一定大于sqrt(x)讥珍。故历极，上述代碼我們也只需要遍歷到sqrt(x)就可以了。若在2~sqrt(x)找不到約數(shù)衷佃，那么一定不存在趟卸。
bool isPrime(int x)
{
if(x==1) return false;
for(int i=2;i*i<=x;i++)
{
if(x%i==0) return false;
}
return true;
}
再進一步進行優(yōu)化，偶數(shù)一定不是質(zhì)數(shù)
bool isPrime(int x)
{
if(x<2) return false;
if(n%2==0) return false;
for(int i=3;i*i<=x;i+=2)
{
if(x%i==0) return false;
}
return true;
}
但當m,n很大的時侯這種方式的數(shù)量級依舊相當大。在一般的機子它不是一秒鐘跑不出結果锄列，它是好幾分鐘都跑不出結果图云。有沒有更有效率的方法呢？
我們可以考慮使用篩法來進行處理邻邮。
埃氏篩
根據(jù)數(shù)學原理：一個合數(shù)總是可以分解成若干個質(zhì)數(shù)的乘積竣况，換個角度去理解，也就是說合數(shù)是某個質(zhì)數(shù)的倍數(shù)筒严。此時如果把質(zhì)數(shù)的倍數(shù)都去掉帕翻，那么剩下的就是質(zhì)數(shù)了。
這樣的篩選方式叫做埃氏篩萝风，也叫埃拉托色尼選篩法嘀掸，是數(shù)學家埃拉托色尼提出的。
代碼思路：
- 從質(zhì)數(shù)2開始進行枚舉
- 如果數(shù)字是質(zhì)數(shù)规惰，將范圍內(nèi)所有該數(shù)的倍數(shù)標記成非質(zhì)數(shù)
- 繼續(xù)向后枚舉睬塌，直到遍歷完范圍內(nèi)所有的數(shù)位置
代碼實現(xiàn)：
#include <iostream>
#include <cstring>
using namespace std;
bool isPrime[10000005]={0};//標記數(shù)組 用來表示數(shù)字是否是質(zhì)數(shù) true-是質(zhì)數(shù) false-不是質(zhì)數(shù)
void aiPrime(int n)
{// 埃氏篩處理n內(nèi)的質(zhì)數(shù)
memset(isPrime,true,sizeof(isPrime));//所有數(shù)字，默認標記為質(zhì)數(shù)
isPrime[1]=false;//修改1的狀態(tài)歇万，1不是質(zhì)數(shù)
for(int i=2;i<=n;i++)//從2開始揩晴，枚舉范圍n內(nèi)的每個數(shù)字
{
if(isPrime[i])//如果i是質(zhì)數(shù)
{//將n范圍內(nèi)所有i的倍數(shù)，標記為非質(zhì)數(shù)
for(int j=2;j*i<=n;j++)
{//打底從兩倍開始,j*i就是i的倍數(shù)
isPrime[i*j]=false;// 標記倍數(shù)為非質(zhì)數(shù)
}
}
}
}
int main(int argc, char** argv) {
int n,m,x;
cin>>n>>m;
aiPrime(n);
for(int i=1;i<=m;i++)
{
cin>>x;
if(isPrime[x])
{
cout<<"yes\n";
}else
{
cout<<"no\n";
}
}
return 0;
}
