用c语言怎么判断素数

如何用 C 语言判断素数

判断给定数字是否为素数是计算机编程中一个常见任务，C 语言提供了多种方法来实现这一功能。

素数定义

素数是一个大于 1 的自然数，并且只能被 1 和它自身整除。

立即学习“C语言免费学习笔记（深入）”；

判断素数的方法

最简单的方法是使用蛮力法：尝试从 2 到待测数字的平方根（包括平方根）对该数字进行取模。如果任何取模操作的结果为 0，则该数字不是素数；否则，该数字是素数。

以下是一个 C 语言实现的蛮力法判断素数函数：

<code class="c">#include <stdio.h>
#include <math.h>
int is_prime(int num) {
    if (num < 2) {
        return 0;
    }
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return 0;
        }
    }
    return 1;
}</code>

另一种更有效的方法称为埃拉托斯特尼筛法，它创建了一个标记数组来跟踪从 2 到给定范围内的每个数字是否为素数。这种方法的复杂度较低，但开销更大。

<code class="c">#include <stdio.h>
void sieve_of_eratosthenes(int n) {
    int primes[n + 1];
    for (int i = 0; i <= n; i++) {
        primes[i] = 1;
    }
    for (int i = 2; i * i <= n; i++) {
        if (primes[i]) {
            for (int j = i * i; j <= n; j += i) {
                primes[j] = 0;
            }
        }
    }
    // 打印素数
    for (int i = 2; i <= n; i++) {
        if (primes[i]) {
            printf("%d ", i);
        }
    }
}</code>