C语言中素数的判定方法（3种）

素数，也称为质数，是指大于 1 且只能被 1 和自身整除的自然数。换句话说，素数只有两个因子：1 和它本身。例如，2、3、5、7、11 和 13 都是素数。
 

素数在数学和计算机科学中扮演着重要角色，尤其在密码学和数据加密领域广泛应用。

判断一个数是否为素数的原理基于其定义，我们需要检查这个数是否只能被 1 和自身整除。实际操作中，我们可以尝试用小于该数的所有整数去除它，如果都不能整除，那么这个数就是素数。
 

下面我们将介绍C语言中判断素数的几种方法，从最基本的方法开始，逐步优化以提高效率。

1. 基本方法

最直接的方法是遍历从 2 到 n-1 的所有数，检查它们是否能整除 n。如果找到任何一个除数，则 n 不是素数；否则，n 是素数。这种方法简单直观，但效率较低，特别是对于较大的数。

#include <stdio.h>

int isPrime(int n) {
    if (n <= 1) return 0;  // 0 和 1 不是素数
    for (int i = 2; i < n; i++) {
        if (n % i == 0) return 0;  // 找到除数，不是素数
    }
    return 1;  // 没有找到除数，是素数
}

int main() {
    int num;
    printf("请输入一个正整数：");
    scanf("%d", &num);
    if (isPrime(num)) {
        printf("%d 是素数\n", num);
    } else {
        printf("%d 不是素数\n", num);
    }
    return 0;
}

输出结果：

请输入一个正整数：17
17 是素数

2. 优化方法 1：减少循环次数

我们可以观察到，如果一个数 n 不是素数，它必然有一个小于或等于 √n 的因子。这是因为如果 n = a * b，其中 a > √n 且 b > √n，那么 a * b > n，这是不可能的。因此，我们只需要检查到 √n 就足够了，这大大减少了循环的次数。

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

int isPrime(int n) {
    if (n <= 1) return 0;
    int sqrtN = (int)sqrt(n);
    for (int i = 2; i <= sqrtN; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    int num;
    printf("请输入一个正整数：");
    scanf("%d", &num);
    if (isPrime(num)) {
        printf("%d 是素数\n", num);
    } else {
        printf("%d 不是素数\n", num);
    }
    return 0;
}

这个优化版本的时间复杂度从 O(n) 降低到了 O(√n)，对于大数来说，效率提升很明显。

3. 优化方法 2：跳过偶数

除了 2 以外，所有的偶数都不是素数。利用这一点，我们可以在检查时跳过所有的偶数，进一步减少循环次数。

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

int isPrime(int n) {
    if (n <= 1) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;  // 如果是偶数（除了2），直接返回不是素数
    int sqrtN = (int)sqrt(n);
    for (int i = 3; i <= sqrtN; i += 2) {  // 只检查奇数
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    int num;
    printf("请输入一个正整数：");
    scanf("%d", &num);
    if (isPrime(num)) {
        printf("%d 是素数\n", num);
    } else {
        printf("%d 不是素数\n", num);
    }
    return 0;
}

这个版本通过跳过偶数，进一步减少了约一半的检查次数，对于大数的判断效率更高。

总结

对于非常大的数，即使是优化后的试除法也可能效率不够。在这种情况下，我们可以使用概率算法，如 Miller-Rabin 素性测试。这种方法可以快速判断一个大数是否为素数，虽然存在极小的错误概率，但在实际应用中已经足够可靠。
 

Miller-Rabin 算法的原理较为复杂，涉及到数论知识，这里不再详细展开。但是对于想深入了解素数判定的读者来说，学习这个算法是很有价值的，尤其是在处理大数或者需要高效率的场景中。
 

总的来说，判断素数的方法从最基本的试除法到各种优化方法，再到高级的概率算法，体现了算法优化的过程。在实际编程中，我们需要根据具体的应用场景和数据规模来选择合适的方法。对于一般的应用，使用优化后的试除法通常已经足够。而在一些特殊领域，如密码学，可能需要使用更高级的算法来处理极大的数。