素数是大于 1 且只能被 1 和自身整除的自然数，例如 2、3、5、7、11、13 等。判断一个整数是否为素数，是 C 语言入门阶段非常典型的算法题，也涉及循环、条件判断、取模运算以及算法复杂度等基础知识。
一、素数判断的基本思路
判断整数 n 是否为素数，本质上是检查它是否存在除 1 和自身之外的其他因数。
最直接的方法是让 i 从 2 开始，一直遍历到 n - 1：
C#includeint main(void) { int n; int isPrime = 1; printf("请输入一个整数："); scanf("%d", &n); if (n < 2) { isPrime = 0; } else { for (int i = 2; i < n; i++) { if (n % i == 0) { isPrime = 0; break; } } } if (isPrime) { printf("%d 是素数 ", n); } else { printf("%d 不是素数 ", n); } return 0; }
这里最关键的运算是：
Cn % i
% 是 C 语言中的取模运算符。如果 n % i == 0，说明 n 可以被 i 整除，因此 n 存在除 1 和自身之外的因数，就可以确定它不是素数。
例如判断 15：
15 % 2 != 0 15 % 3 == 0
发现 15 能被 3 整除后，就没有继续检查的必要，因此使用 break 提前结束循环。
二、为什么不能把 1 判断为素数
素数的定义要求一个数必须大于 1，并且恰好拥有两个正因数：1 和它本身。
因此：
1：只有因数 1，不是素数 2：因数为 1、2，是素数 3：因数为 1、3，是素数 4：因数为 1、2、4，不是素数
代码中通常需要优先处理：
Cif (n < 2) { isPrime = 0; }
这样可以避免将 0、1 以及负数错误地判定为素数。
三、将循环范围优化到 n / 2
实际上，没有必要检查 2 到 n - 1 的所有数字。
如果 n 是合数，并且存在因数 i 满足：
n = i × j
那么至少有一个因数不会超过 n / 2。因此可以将循环条件改成：
Cfor (int i = 2; i <= n / 2; i++)
完整代码如下：
C#includeint main(void) { int n; int isPrime = 1; scanf("%d", &n); if (n < 2) { isPrime = 0; } else { for (int i = 2; i <= n / 2; i++) { if (n % i == 0) { isPrime = 0; break; } } } if (isPrime) { printf("%d 是素数 ", n); } else { printf("%d 不是素数 ", n); } return 0; }
这种写法比遍历到 n - 1 更高效，但还可以继续优化。
四、为什么只需要判断到平方根
素数判断中非常重要的一个优化是：只检查 sqrt(n) 以内的整数。
假设一个数 n 不是素数，那么它可以表示为：
n = a × b
如果 a 和 b 都大于 sqrt(n)，那么：
a × b > sqrt(n) × sqrt(n) > n
这与 a × b = n 矛盾。
因此，只要 n 存在非 1 和自身的因数，就一定可以在 sqrt(n) 以内找到一个因数。
例如判断 100：
100 = 2 × 50 100 = 4 × 25 100 = 5 × 20 100 = 10 × 10
只检查到 10 就足够了。
五、使用平方根函数实现
可以使用 sqrt()：
C#include#include int main(void) { int n; int isPrime = 1; scanf("%d", &n); if (n < 2) { isPrime = 0; } else { for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) { isPrime = 0; break; } } } if (isPrime) { printf("%d 是素数 ", n); } else { printf("%d 不是素数 ", n); } return 0; }
这种实现思路非常直观，不过在循环条件中反复调用 sqrt(n) 并没有必要。对于大量判断操作，更推荐避免重复计算。
六、使用 i * i <= n 进一步优化
更常见的写法是：
Cfor (int i = 2; i * i <= n; i++)
完整实现：
C#includeint main(void) { int n; int isPrime = 1; scanf("%d", &n); if (n < 2) { isPrime = 0; } else { for (int i = 2; i * i <= n; i++) { if (n % i == 0) { isPrime = 0; break; } } } if (isPrime) { printf("%d 是素数 ", n); } else { printf("%d 不是素数 ", n); } return 0; }
与 sqrt() 方案相比，这种代码不需要引入
不过，对于可能非常大的整数类型，需要注意 i * i 本身可能发生整数溢出。此时可以写成：
Cfor (int i = 2; i <= n / i; i++)
这样可以避免计算 i * i 时超过整数类型的表示范围。
七、跳过偶数进一步减少判断次数
除了 2 之外，所有偶数都不是素数。因此可以单独处理 2，然后只检查奇数：
C#includeint isPrime(int n) { if (n < 2) { return 0; } if (n == 2) { return 1; } if (n % 2 == 0) { return 0; } for (int i = 3; i <= n / i; i += 2) { if (n % i == 0) { return 0; } } return 1; } int main(void) { int n; printf("请输入一个整数："); scanf("%d", &n); if (isPrime(n)) { printf("%d 是素数 ", n); } else { printf("%d 不是素数 ", n); } return 0; }
这里的核心优化有三层：
1. n < 2 直接排除 2. 2 单独处理 3. 后续只检查奇数，并且只检查到平方根
这种方式已经足以应对绝大多数 C 语言素数判断场景。
八、为什么推荐封装成 isPrime 函数
将素数判断封装成独立函数，可以让程序结构更加清晰：
Cint isPrime(int n)
函数返回 1 表示是素数，返回 0 表示不是素数。
这样除了判断单个数字，还可以非常方便地应用到其他程序中，例如输出某个范围内的所有素数：
C#includeint isPrime(int n) { if (n < 2) { return 0; } if (n == 2) { return 1; } if (n % 2 == 0) { return 0; } for (int i = 3; i <= n / i; i += 2) { if (n % i == 0) { return 0; } } return 1; } int main(void) { for (int i = 1; i <= 100; i++) { if (isPrime(i)) { printf("%d ", i); } } return 0; }
运行后可以得到：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
九、不同素数判断算法的效率比较
假设待判断的数字为 n，常见实现方式可以进行如下比较：
| 判断方式 | 大致判断范围 | 时间复杂度 | 特点 |
|---|---|---|---|
| 遍历到 n-1 | 2 ~ n-1 | O(n) | 最基础，效率较低 |
| 遍历到 n/2 | 2 ~ n/2 | O(n) | 减少一部分循环 |
| 遍历到平方根 | 2 ~ √n | O(√n) | 推荐使用 |
| 平方根 + 跳过偶数 | 奇数至 √n | O(√n) | 实际判断次数更少 |
对于单次素数判断，O(√n) 已经是非常实用的方案。
例如：
n = 1,000,000 √n = 1,000
原始算法最坏情况下可能需要进行接近百万次除法运算，而平方根算法最多只需要检查约 1000 个候选因数。跳过偶数之后，实际检查次数还会进一步减少。
十、判断大量数字时的算法选择
如果程序只判断一个整数是否为素数，使用试除法即可。
如果需要判断大量连续整数，例如求：
1 到 1000000
范围内的所有素数，逐个调用 isPrime() 虽然可以实现，但效率并不是最高。
这种情况下，可以考虑埃拉托斯特尼筛法。
基本思路是先假设所有大于 1 的数字都是素数，然后从最小素数 2 开始，把它的倍数全部标记为合数。接着找到下一个没有被标记的数字，继续执行。
示例：
C#include#define MAX 100 int main(void) { int prime[MAX + 1]; for (int i = 0; i <= MAX; i++) { prime[i] = 1; } prime[0] = prime[1] = 0; for (int i = 2; i <= MAX / i; i++) { if (prime[i]) { for (int j = i * i; j <= MAX; j += i) { prime[j] = 0; } } } for (int i = 2; i <= MAX; i++) { if (prime[i]) { printf("%d ", i); } } return 0; }
筛法适合一次性生成一个范围内的全部素数，其核心复杂度约为：
O(n log log n)
当数据范围较大且需要大量查询时，筛法通常比逐个进行试除判断更加合适。
十一、C语言实现素数判断时的常见错误
错误一：把 1 当作素数
例如直接写：
Cint isPrime = 1;
然后没有处理 n < 2 的情况，就可能错误地将 1 判定为素数。
应增加：
Cif (n < 2) { return 0; }
错误二：循环从 1 开始
如果写成：
Cfor (int i = 1; i <= n; i++)
那么任何整数都可以被 1 整除，这个判断没有实际意义。
判断素数时应该从：
Ci = 2
开始。
错误三：找到因数后仍然继续循环
一旦发现：
Cn % i == 0
就已经确定 n 不是素数，没有继续计算的必要：
Creturn 0;
或者：
Cbreak;
都可以减少不必要的运算。
错误四：忽略负数和 0
素数必须大于 1，因此：
-10、-3、0、1
都不是素数。
错误五：平方根判断出现整数溢出
对于普通的 int 数据，i * i <= n 通常足够使用，但处理接近类型上限的数据时，应考虑：
Ci <= n / i
这种写法能够降低乘法溢出的风险。
十二、推荐的实用实现
综合代码可读性、执行效率和安全性，一个适合日常使用的版本如下：
C#includeint isPrime(int n) { if (n < 2) { return 0; } if (n == 2) { return 1; } if (n % 2 == 0) { return 0; } for (int i = 3; i <= n / i; i += 2) { if (n % i == 0) { return 0; } } return 1; } int main(void) { int n; printf("请输入一个整数："); if (scanf("%d", &n) != 1) { printf("输入无效 "); return 1; } printf("%d %s素数 ", n, isPrime(n) ? "是" : "不是"); return 0; }
这份代码把素数判断独立成 isPrime() 函数，同时利用提前返回、排除偶数、平方根范围等方法降低计算量，适合作为 C 语言学习和实际项目中的基础实现。
十三、算法优化的核心原则
C语言素数判断看似简单，但其中包含了几个非常典型的算法优化思想。
第一是缩小搜索范围。从 n - 1 缩小到 √n，可以显著减少循环次数。
第二是排除不可能的情况。除了 2 之外的偶数不可能成为素数，因此可以直接跳过。
第三是尽早结束。一旦发现能够整除 n 的因数，就立即返回结果。
第四是根据任务规模选择算法。单个数字判断适合试除法；连续范围内寻找大量素数，则可以考虑埃拉托斯特尼筛法。
掌握这些思路后，C语言中的素数判断就不再只是简单的循环练习，而可以进一步理解时间复杂度、边界条件、整数溢出以及算法优化之间的关系。