C 语言中检查素数的方法有三种：暴力算法：遍历从 2 到平方根的所有整数，若能整除则非素数。费马小定理：a^(p-1) % p = 1，若恒等则为素数。Miller-Rabin 算法：更有效，但实现较复杂。

如何在 C 语言中检查素数

什么是素数？
素数是指除自身和 1 之外，不能被其他正整数整除的自然数。

C 语言中检查素数的方法

1. 暴力算法

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

• 遍历从 2 到 待检测数的平方根的所有整数。
• 如果待检测数能被遍历的整数整除，则它不是素数。
• 如果待检测数无法被任何遍历的整数整除，则它是一个素数。

代码实现：

#include <stdio.h>
#include <math.h>

int is_prime(int num) {
    if (num <= 1) return 0;
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) return 0;
    }
    return 1;
}

2. 费马小定理

• 对于任何素数 p 和任何整数 a，a^(p-1) % p = 1。

代码实现：

#include <stdio.h>

int is_prime(int num) {
    if (num <= 1) return 0;
    for (int i = 2; i < num; i++) {
        if (pow(i, num-1) % num != 1) return 0;
    }
    return 1;
}

3. Miller-Rabin 算法

• 这是检查素数的一种更有效的算法，但实现起来比较复杂。

代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int is_prime(int num) {
    if (num <= 1) return 0;
    if (num <= 3) return 1;
    if (num % 2 == 0 || num % 3 == 0) return 0;

    int s = 0;
    uint64_t d = num-1;
    while (d % 2 == 0) {
        s++;
        d /= 2;
    }

    for (int i = 0; i < 20; i++) {
        int a = rand() % (num-1) + 1;
        uint64_t x = powmod(a, d, num);
        if (x == 1 || x == num-1) continue;
        int j = 1;
        while (j < s && x != num-1) {
            x = powmod(x, 2, num);
            if (x == 1) return 0;
            j++;
        }
        if (x != num-1) return 0;
    }

    return 1;
}