如何用C语言求素数

JGYOA • 2025-04-25 15:26 • 编程

一、素数的概念

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

原创文章，作者：JGYOA，如若转载，请注明出处：https://www.506064.com/n/372964.html