質(zhì)數(shù)判斷

我們來看這么一道問題：

給定一個(gè)范圍N，你需要處理M個(gè)某數(shù)字是否為質(zhì)數(shù)的詢問（每個(gè)數(shù)字均在范圍1-N內(nèi)）N<=10000000，M<=100000

首先很容易聯(lián)想到使用枚舉法來確定題目的整體框架

for( i: 1~m)
{
    cin>>x;
    if(x是質(zhì)數(shù))
    {
        yes;
    }else
    {
        no;
    }
}

關(guān)鍵在于質(zhì)數(shù)判斷部分。

質(zhì)數(shù)的判斷問題我們可以從定義出發(fā)。質(zhì)數(shù)，又稱素?cái)?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;
}

稍微計(jì)算下整體的時(shí)間復(fù)雜度，可以發(fā)現(xiàn)用時(shí)會(huì)比較多，那么我們可以思考下優(yōu)化的地方。整體框架確定后，能優(yōu)化的地方可從質(zhì)數(shù)判斷入手。思考，一個(gè)數(shù)去除以比它的一半還要大的數(shù)，一定是除不盡的，因此，除到x/2就夠了。

再改進(jìn)一下，一個(gè)數(shù)若可以進(jìn)行因數(shù)分解，那么分解得到的兩個(gè)數(shù)一個(gè)范圍小于sqrt(x),另一個(gè)一定大于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;
}

再進(jìn)一步進(jìn)行優(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;
}

但當(dāng)m,n很大的時(shí)侯這種方式的數(shù)量級(jí)依舊相當(dāng)大。在一般的機(jī)子它不是一秒鐘跑不出結(jié)果，它是好幾分鐘都跑不出結(jié)果。有沒有更有效率的方法呢？

我們可以考慮使用篩法來進(jìn)行處理。

埃氏篩

根據(jù)數(shù)學(xué)原理：一個(gè)合數(shù)總是可以分解成若干個(gè)質(zhì)數(shù)的乘積，換個(gè)角度去理解，也就是說合數(shù)是某個(gè)質(zhì)數(shù)的倍數(shù)。此時(shí)如果把質(zhì)數(shù)的倍數(shù)都去掉，那么剩下的就是質(zhì)數(shù)了。

這樣的篩選方式叫做埃氏篩，也叫埃拉托色尼選篩法，是數(shù)學(xué)家埃拉托色尼提出的。

代碼思路：

1. 從質(zhì)數(shù)2開始進(jìn)行枚舉
2. 如果數(shù)字是質(zhì)數(shù)，將范圍內(nèi)所有該數(shù)的倍數(shù)標(biāo)記成非質(zhì)數(shù)
3. 繼續(xù)向后枚舉，直到遍歷完范圍內(nèi)所有的數(shù)位置

代碼實(shí)現(xiàn)：

#include <iostream>
#include <cstring>
using namespace std;

bool isPrime[10000005]={0};//標(biāo)記數(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ù)字，默認(rèn)標(biāo)記為質(zhì)數(shù) 
    isPrime[1]=false;//修改1的狀態(tài)，1不是質(zhì)數(shù)
    
    for(int i=2;i<=n;i++)//從2開始，枚舉范圍n內(nèi)的每個(gè)數(shù)字 
    {
        if(isPrime[i])//如果i是質(zhì)數(shù)
        {//將n范圍內(nèi)所有i的倍數(shù)，標(biāo)記為非質(zhì)數(shù) 
            for(int j=2;j*i<=n;j++)
            {//打底從兩倍開始,j*i就是i的倍數(shù) 
                isPrime[i*j]=false;// 標(biāo)記倍數(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;
}