C++判斷素數方法

一、什麼是素數

素數是只能被1和自身整除的數，比如2、3、5、7、11等。判斷一個數是否為素數一直是數學裡的一個熱門問題，也是我們在演算法和編程中經常遇到的問題之一。

二、判斷素數的方法

C++中常用的判斷素數的方法有兩種：試除法和Eratosthenes篩法。

三、試除法

試除法是最基本的判斷素數的方法，其思想是：用2~(n-1)的整數去除n，如果都除不盡，那麼n就是素數。C++代碼如下：

bool isPrime(int n){
    for(int i=2;i<n;i++){
        if(n%i==0) return false; // 如果n能被i整除，說明n不是素數
    }
    return true;
}

這種方法雖然簡單易懂，但效率較低，當n很大時，計算量會非常大。

四、Eratosthenes篩法

Eratosthenes篩法是一種比較高效的判斷素數的方法，具體步驟如下：

1. 建立一個長度為n+1的bool數組is_prime，初始化為true。

2. 從2開始，依次將小於等於n的所有素數的倍數標記為false，這些數肯定不是素數。

3. 遍曆數組，未被標記為false的數就是素數。

C++代碼如下：

void eratosthenes(int n){
    bool is_prime[n+1];
    memset(is_prime,true,sizeof(is_prime)); // 將is_prime數組全部初始化為true
    for(int i=2;i*i<=n;i++){ // 從2開始，標記小於等於n的所有素數的倍數為false
        if(is_prime[i]){
            for(int j=i*i;j<=n;j+=i){
                is_prime[j]=false;
            }
        }
    }
    for(int i=2;i<=n;i++){ // 遍曆數組，未被標記為false的數就是素數
        if(is_prime[i]){
            cout<<i<<" ";
        }
    }
}

使用Eratosthenes篩法判斷素數的時間複雜度為O(nloglogn)，比試除法效率高很多。

五、總結

以上是C++常用的兩種判斷素數的方法，試除法簡單易懂但效率較低，適用於小數判斷。Eratosthenes篩法複雜度較低，適用於大數判斷。在實際應用中，應根據具體情況選擇合適的方法。