素数是大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做素数，比如2、3、5、7都是常见的素数。判断一个数是否为素数是C语言入门阶段常见的编程练习，也可以通过不同算法实现批量求解指定范围内的所有素数。
基础方法：遍历判断单个素数
最直观的思路是从2开始遍历到n-1，判断是否存在能整除n的数，如果存在则n不是素数，否则n是素数。需要注意1不是素数，2是最小的素数。
实现单个素数判断的代码示例如下：
#include <stdio.h>
// 判断是否为素数的函数，是素数返回1，不是返回0
int isPrime(int n) {
// 1不是素数，直接返回0
if (n <= 1) {
return 0;
}
// 从2遍历到n-1
for (int i = 2; i < n; i++) {
// 如果存在能整除n的数，说明不是素数
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-1存在很多不必要的判断，比如判断100是否为素数，只需要判断到10即可，因为如果100存在大于10的因数，对应的另一个因数一定小于10。因此遍历到sqrt(n)就能完成判断，减少循环次数。
优化后的判断函数代码如下：
#include <stdio.h>
#include <math.h>
int isPrime(int n) {
if (n <= 1) {
return 0;
}
// 遍历到sqrt(n)即可，需要包含math.h头文件
for (int i = 2; i <= sqrt(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;
}
批量求解：埃氏筛法
如果需要求解1到n之间的所有素数，逐个判断的效率较低，埃氏筛法是更高效的批量求解方法。核心思路是创建一个标记数组，初始假设所有数都是素数，然后从2开始，将每个素数的倍数都标记为合数，最终未被标记的数就是素数。
埃氏筛法实现1到100所有素数的代码示例如下：
#include <stdio.h>
#include <string.h>
#define MAX 101
int main() {
int isPrime[MAX];
// 初始假设所有数都是素数，0表示素数，1表示合数
memset(isPrime, 0, sizeof(isPrime));
isPrime[0] = isPrime[1] = 1; // 0和1不是素数
// 埃氏筛法核心逻辑
for (int i = 2; i < MAX; i++) {
if (isPrime[i] == 0) { // 如果i是素数
// 将i的倍数都标记为合数
for (int j = i * 2; j < MAX; j += i) {
isPrime[j] = 1;
}
}
}
// 输出1到100的所有素数
printf("1到100之间的素数有：n");
for (int i = 2; i < MAX; i++) {
if (isPrime[i] == 0) {
printf("%d ", i);
}
}
printf("n");
return 0;
}
不同方法的适用场景
如果是判断单个数字是否为素数，平方根判断法的效率已经足够；如果需要批量求解较大范围内的所有素数，埃氏筛法的时间复杂度更低，更适合处理大规模数据。在实际编程中可以根据需求选择合适的实现方式。