C 语言求素数是期末考试 上机考试 计算机二级的高频编程大题,素数也叫质数,定义是大于 1 的自然数,除了 1 和它本身之外,不能被其他任何整数整除,最小素数是 2。基础写法是循环试除,拿数字 n 依次从 2 试除到 n 减 1,如果中途可以整除,说明不是素数,如果全部都不能整除,就是素数,考试还经常要求优化版本,试除只需要到根号 n,减少循环次数,同时题目常考两种题型,判断单个数字是不是素数,还有输出指定范围内全部素数,理解判断逻辑之后,两种题型都可以快速改写,注意边界坑点,数字小于 2 直接判定不是素数,2 本身是素数,这个是读程序题经常挖坑的地方。
素数判断核心原理
素数判断逻辑
对于数字 n
1 如果 n <= 1,不是素数
2 如果 n == 2,是素数
3 如果 n 是偶数,大于 2 的偶数都不是素数
4 用 i 从 2 开始试除 n % i,如果余数等于 0,代表可以整除,不是素数
5 循环全部结束,没有找到可以整除的数,就是素数
优化思路
不需要试除到 n 减 1,只需要试除到 sqrt (n),因为如果 n 有大于根号 n 的因子,那么对应的另一个因子一定小于根号 n,这样循环次数大幅减少,代码效率更高,考试写优化版本更容易拿高分。
版本一 基础版 判断单个数字是否素数
include
int main()
{
int n, i, flag = 1;
scanf("%d", &n);
if(n <= 1)
{
flag = 0;
}
for(i = 2; i < n; i++)
{
if(n % i == 0)
{
flag = 0;
break;
}
}
if(flag == 1)
{
printf("%d是素数", n);
}
else
{
printf("%d不是素数", n);
}
return 0;
}
版本二 优化版 试除到根号 n
include
include
int main()
{
int n, i, flag = 1;
scanf("%d", &n);
if(n <= 1)
{
flag = 0;
}
for(i = 2; i <= sqrt(n); i++)
{
if(n % i == 0)
{
flag = 0;
break;
}
}
if(flag == 1)
{
printf("%d是素数", n);
}
else
{
printf("%d不是素数", n);
}
return 0;
}
注意 使用 sqrt 函数需要引入 math.h 头文件,部分编译器编译的时候需要加数学库参数。
版本三 输出 1 到 n 之间所有素数
include
int main()
{
int n, i, j, flag;
scanf("%d", &n);
for(i = 2; i <= n; i++)
{
flag = 1;
for(j = 2; j
版本对比表格
| 版本 | 试除范围 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|
| 基础版 | 2 到 n-1 | 代码简单,容易理解 | 循环次数多 | 初学,考试基础题 |
| 优化版 | 2 到 sqrt (n) | 运行效率高 | 需要 math.h 头文件 | 高分优化写法 |
| 区间输出版 | 双层循环 | 可以批量打印素数 | 双层循环 | 范围输出素数大题 |
常见易错点汇总
| 错误类型 | 错误描述 | 修正方式 |
|---|---|---|
| 边界错误 | 忘记 n<=1 不是素数,或者把 2 判定成非素数 | 单独处理小于 2 和数字 2 |
| 忘记 break | 找到整除之后继续循环,flag 判断出错 | 一旦整除立刻 break 跳出 |
| flag 初始化错误 | 每次外层循环没有重置 flag 为 1 | 每个数字判断前 flag 重新赋值 1 |
| 取模写错 | 写成 n/i,不是 n% i | 判断整除必须使用取模 % |
| sqrt 类型问题 | 整数和浮点数比较出错 | 注意 sqrt 返回 double 类型 |
拓展补充
还有埃氏筛法,适合一次性求大范围素数,效率比试除法更高,但是期末考试上机一般优先考试除法,埃氏筛法属于进阶内容,如果老师没有要求,优先掌握试除法代码。
【常见问题】
问题 1 C 语言求素数代码里面 flag 变量作用是什么
回答 1 C 语言求素数代码里面 flag 是标记变量,初始为 1 代表默认是素数,如果找到可以整除因子,就把 flag 改成 0,循环结束通过 flag 判断结果,是 C 语言求素数代码经典写法。
问题 2 C 语言求素数代码为什么要 break
回答 1 C 语言求素数代码一旦发现 n 可以被 i 整除,就已经确定不是素数,不需要继续试除,使用 break 立刻跳出循环,节省运算,是 C 语言求素数代码关键语句。
问题 3 C 语言求素数代码优化为什么只需要到根号 n
回答 1 C 语言求素数代码优化原理是如果数字存在大于根号 n 的因数,必然配套存在小于根号 n 的因数,所以只需要试除到 sqrt (n),提升 C 语言求素数代码运行效率。
问题 4 C 语言求素数代码最小素数是多少
回答 1 C 语言求素数代码要记住最小素数是 2,1 和小于 1 的数字都不是素数,这个边界条件是 C 语言求素数代码考试经常设置的考点。
【免责申明】
本文内容仅作为 C 语言求素数代码备考学习参考,代码示例适配主流 gcc 环境,不同编译器编译 sqrt 函数参数略有差异,考试答题以本校教材要求为准,学习使用产生的相关问题由使用者自行承担。


