如何用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語言實現求素數的過程也可以幫助讀者更好地理解算法的實現過程。