首页 > 甄选问答 >

问 C 语言求素数代码 经典编程题详解

2026-11-05 08:42:06
最佳答案

答

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 函数参数略有差异,考试答题以本校教材要求为准,学习使用产生的相关问题由使用者自行承担。