如何用C語言求素數

一、素數的概念

素數是指在大於1的自然數中，除了1和它本身以外，不能被其他自然數整除的數。比如2、3、5、7等都是素數。

為了方便，我們用n代表待判斷的數。判斷n是否為素數，就是判斷n能否被2到n-1之間的任何一個數整除，如果不能，那麼n就是素數。

二、常見的求素數演算法

1. 直接判斷法

bool is_prime(int n){
    if(n <= 1){  //小於等於1的數不是素數
        return false;
    }
    for(int i=2; i<n; i++){
        if(n % i == 0){  //如果n能被i整除，那麼n不是素數
            return false;
        }
    }
    return true;
}

直接判斷法是一種比較簡單的方法，但是對於大的素數來說，速度會比較慢。

2. 厄拉多塞篩法

厄拉多塞篩法的基本思想是從2開始，將每個素數的倍數都標記為合數，以達到篩選素數的目的。具體步驟如下：

（1）先將 2~n 中的所有整數寫下來；

（2）先把 2 的倍數都打上標記，除了2；

（3）再把 3 的倍數都打上標記，除了3；

（4）接著找下一個素數 5，重複上述過程；

（5）一直重複下去，直到某個數的平方大於n為止。此時，還沒有被標記的數就是素數。

void prime_sieve(int n, bool *is_prime){
    memset(is_prime, true, (n+1)*sizeof(bool));
    is_prime[0] = false;
    is_prime[1] = false;
    for(int i=2; i*i<=n; i++){
        if(is_prime[i]){
            for(int j=i*i; j<=n; j+=i){
                is_prime[j] = false;
            }
        }
    }
}

三、比較兩種演算法的效率

下面我們來比較一下這兩種演算法的效率。測試數據為n=1,000,000。

#include 
#include 
#define N 1000000

int main(){
    bool is_pri[N+1];
    clock_t start, end;
    double duration;

    start = clock();
    prime_sieve(N, is_pri);
    end = clock();
    duration = (double)(end - start) / CLOCKS_PER_SEC;
    printf("prime_sieve: %.5fs\n", duration);

    start = clock();
    for(int i=1; i<=N; i++){
        is_prime(i);
    }
    end = clock();
    duration = (double)(end - start) / CLOCKS_PER_SEC;
    printf("is_prime: %.5fs\n", duration);

    return 0;
}

測試結果如下所示：

prime_sieve: 0.00800s
is_prime:  11.91400s

可以看出，厄拉多塞篩法的效率遠高於直接判斷法。

四、總結

求素數是演算法中比較基礎的部分，在實際應用中也經常用到。本文介紹了兩種常見的求素數演算法，包括直接判斷法和厄拉多塞篩法，並比較了它們的效率。用C語言實現求素數的過程也可以幫助讀者更好地理解演算法的實現過程。