判斷素數的幾種方法的總結

素數，又稱質數，定義是：除了1和它本身以外不再有其他的除數整除。

方法一

按照定義，從2到n-1判斷有沒有能整除n的數。如果有，則不是素數，否則，是素數

bool is_prime(int n){
    if (n < 2){
        return false;
    }
    int i;
    for (i = 2; i < n; i++){
        if (n%i == 0){
            return false;
        }
    }
    return true;
}      

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12

算法複雜度：O(n)

方法二

還是按照定義，不過是從2一直算到sqrt(n)，這樣算法複雜度降低了很多

bool is_prime(int n){
    if (n < 2){
        return false;
    }
    int i;
    for (i = 2; i*i <= n; i++){
        if (n%i == 0){
            return false;
        }
    }
    return true;
}      

方法三

米勒拉賓素數測試的方法

米勒拉賓證明起來很麻煩(準确的說是部落客也不會 -_-#)

直接上模闆吧

int tab[]={2, 3, 5, 7};
long long qpow(int a, int b, int r)  //(a^b)%r  快速幂取模
{
    long long ret = 1, tmp = a;
    while(b)
    {
        if (b&1)
            ret = ret*tmp%r;
        tmp = tmp*tmp%r;
        b >>= 1;
    }
    return ret; 
}
bool  Miller_Rabbin(int n, int a)//米勒拉賓素數測試 
{
    int r = 0, s = n-1, j;
    long long k;
    if(n%a == 0)    return false;
    while((s&1) == 0)
    {
        s >>= 1;
        r++;
    }
    k = qpow(a, s, n);
    if(k == 1)  return true;
    for (j = 0; j < r; j++, k=k*k%n)
        if (k == n-1)
            return true;
    return false;
}
bool Isprime(int n)//判斷是否是素數 
{
    for (int i = 0; i < 4; i++)
    {
        if (n == tab[i])
            return true;
        if (!Miller_Rabbin(n, tab[i]))
            return false;
    }
    return true;
}      

• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41

方法四

上面幾種方法都隻能判斷一個數是不是素數，當需要判斷1-n裡面有多少素數時，就會很麻煩，有一種較為簡單的方法就是Eratosthenes篩法

如果一個數是素數，那麼這個數的倍數一定不是素數，就是這個思想，把所有的非素數都去掉

bool flag[N];
void fun(){
    long long i, j;
    for (i = 0; i < N; i++){
        flag[i] = true;
    }
    flag[0] = flag[1] = false;
    for (i = 2; i < N; i++){
        if (!flag[i])   continue;
        for (j = i*i; j < N; j += i){
            flag[j] = false;
        }
    }
}      

算法複雜度O(n*log log n) 

但是這個算法有一個備援的地方：比如合數10，在枚舉2的時候我們判定了一次，在枚舉5的時候我們又判定了一次。是以使得其時間複雜度比O(n)要高。

方法五

我們可以知道，任意一個正整數k，若k≥2，則k可以表示成若幹個質數相乘的形式。Eratosthenes篩法中，在枚舉k的每一個質因子時，我們都計算了一次k，進而造成了備援。是以在改進算法中，隻利用k的最小質因子去計算一次k。 

與Eratosthenes篩法不同的是，對于外層枚舉i，無論i是質數，還是是合數，我們都會用i的倍數去篩。但在枚舉的時候，我們隻枚舉i的質數倍。比如2i,3i,5i,…，而不去枚舉4i,6i…，原因我們後面會講到。

此外，在從小到大依次枚舉質數p來計算i的倍數時，我們還需要檢查i是否能夠整除p。若i能夠整除p，則停止枚舉。

利用該算法，可以保證每個合數隻會被枚舉到一次。我們可以證明如下命題：

假設一個合數k=M*p1，p1為其最小的質因子。則k隻會在i=M，primeList[j]=p1時被篩掉一次。

首先會在i=M，primeList[j]=p1時被篩掉是顯然的。因為p1是k的最小質因子，是以i=M的所有質因子也≥p1。于是j循環在枚舉到primeList[j]=p1前不會break，進而一定會在i=M，primeList[j]=p1時被篩掉

int primelist[N], primecount = 0;
bool isprime[N];
void eular(int n){
    int i, j;
    for (i = 0; i <= n; i++){
        isprime[i] = true;
    }
    isprime[0] = isprime[1] = false;
    for (i = 2; i <= n; i++){
        if (isprime[i]){
            primelist[primecount++] = i;
        }
        for (j = 0; j < primecount; j++){
            if (i*primelist[j] > n){
                break;
            }
            isprime[i*primelist[j]] = false;
            if (i%primelist[j]==0){
                break;
            }
        }
    }
}