如何用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

   
直接判断法是一种比较简单的方法，但是对于大的素数来说，速度会比较慢。


   
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语言实现求素数的过程也可以帮助读者更好地理解算法的实现过程。