C语言素数判定（从零开始掌握高效判断素数的C语言算法）

方法一：最基础的暴力判断法

最直观的方法是从2开始，逐个检查到n-1，看是否有能整除n的数。如果有，则n不是素数；否则是素数。

#include <stdio.h>int isPrime(int n) {    if (n <= 1) return 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;}

这个方法简单易懂，但效率较低，特别是当n很大时，循环次数非常多。

方法二：优化版——只需检查到√n

数学上可以证明：如果一个数n有因数，那么至少有一个因数小于或等于√n。因此，我们只需检查从2到√n之间的整数即可。这是最常用的C语言素数判定优化方法。

#include <stdio.h>#include <math.h>int isPrime(int n) {    if (n <= 1) return 0;    if (n == 2) return 1; // 2是唯一的偶素数    if (n % 2 == 0) return 0; // 排除其他偶数        // 只需检查奇数，从3到√n    for (int i = 3; i <= sqrt(n); 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;}

这个版本大大减少了循环次数。例如，判断10001是否为素数，原来要循环10000次，现在只需循环约50次（√10001 ≈ 100，再跳过偶数就是50次左右）。

常见误区与注意事项

• 不要忘记处理特殊情况：1不是素数，2是素数。
• 使用sqrt(n)时记得包含<math.h>头文件。
• 对于大范围素数查找（如找出1~10000内所有素数），建议使用“埃拉托斯特尼筛法”等更高级的素数算法。

总结

通过本教程，你应该已经掌握了如何用C语言编程教程中最基础也最重要的技巧之一——判断素数。无论是初学者练习循环结构，还是准备面试题，C语言判断素数都是一个经典且实用的问题。

记住：理解原理比死记代码更重要。动手多写几遍，尝试修改边界条件，你会对这类问题有更深的理解！