核心结论就是素数也叫质数,定义是大于 1 的自然数,除了 1 和它本身之外,没有其他可以整除的因数,在 C 语言实现判断素数的时候,最基础写法就是遍历试除法,进阶优化是只遍历到平方根,还有埃氏筛法适合批量找出范围内全部素数,上机考试最常考的是试除法,核心思路就是从 2 开始逐个尝试能不能被这个数整除,如果存在可以整除的数,就不是素数,如果全部都不能整除,就是素数,编写代码的时候一定要单独处理小于等于 1 的特殊情况,很多同学漏掉这个边界判断导致结果出错。之所以要做平方根优化,是因为如果数字 n 存在一对因数 a 和 b,a 乘 b 等于 n,那么其中一定有一个因数小于或者等于根号 n,如果根号 n 以内都找不到因数,大于根号 n 的位置也不可能存在其他因数,这样可以大幅减少循环次数,提升程序运行效率。
一 素数基础定义与特殊边界
素数必须满足全部条件
第一 数值大于 1
第二 只能被 1 和自身整除
特殊情况
0 和 1 都不是素数
2 是唯一的偶素数
大于 2 的偶数全部都不是素数
二 基础试除法
基础试除法逻辑
输入数字 n
如果 n 小于等于 1,直接判定不是素数
循环变量 i 从 2 开始,循环到 n 减 1
判断 n 对 i 取模是否等于 0
如果取模等于 0,说明可以整除,标记不是素数,提前跳出循环
循环结束之后,如果没有找到可以整除的因数,就是素数
缺点就是循环次数多,数字很大的时候运行慢,适合入门理解原理。
三 优化版试除法 遍历到平方根
优化逻辑
循环上限改成根号 n,使用 sqrt 函数,需要引入 math.h 头文件
循环 i 从 2 到根号 n
如果 n 对 i 取模等于 0,判定非素数
额外还可以继续优化,找到 2 可以整除之后,后续只遍历奇数,跳过偶数,进一步减少循环次数
四 埃氏筛法 批量求素数
埃氏筛法适合一次性找出某个区间内所有素数,不是单独判断某一个数字
原理
建立标记数组,初始全部标记为素数
从 2 开始,把 2 所有倍数标记成非素数
再取下一个未被标记的数字,把它所有倍数标记成非素数
一直处理到根号上限,最后剩下标记为素数的数字就是全部质数
适合题目要求输出 1 到 N 所有素数的题型。
五 三种方法对照表
| 方法 | 适用场景 | 优点 | 缺点 |
|---|---|---|---|
| 基础试除法 | 单个数字判断 | 代码简单容易理解 | 循环次数多效率低 |
| 平方根优化试除法 | 单个数字判断 | 循环次数大幅减少 | 需要调用 sqrt 函数 |
| 埃氏筛法 | 批量查找区间全部素数 | 批量处理效率高 | 需要数组占用内存 |
六 详细编码步骤
第一步 引入 stdio.h,如果使用 sqrt 函数还要引入 math.h
第二步 定义变量,接收用户输入的整数 n,定义标记变量,一般 flag 标记,flag 等于 1 代表是素数,flag 等于 0 代表不是素数
第三步 边界判断,如果 n 小于等于 1,flag 赋值为 0
第四步 开启 for 循环,按照选定算法设置循环起始值和终止条件
第五步 在循环内部做取模判断,如果 n% i 等于 0,修改 flag 并且 break 跳出循环
第六步 循环结束之后,根据 flag 的值,打印结果,输出是素数或者不是素数
第七步 如果是埃氏筛法,额外定义布尔或者 int 标记数组,完成倍数标记之后遍历数组输出所有素数
七 高频踩坑要点
第一 漏掉 n 等于 1 的判断,把 1 错误判定成素数
第二 使用 sqrt 的时候没有引入 math.h,编译警告报错
第三 循环终止条件写错,循环到 n 而不是根号 n,或者边界多一次少一次
第四 取模运算符写错,把 n% i 写成 i% n,判断逻辑完全错误
第五 埃氏筛法数组大小开太小,下标越界
第六 没有提前 break,找到因数之后仍然继续循环,虽然结果一般不变,但是浪费运算时间
问题 1 c 语言中判断素数的方法里为什么 2 是特殊素数
回答 1 c 语言中判断素数的方法里面,2 是唯一偶数素数,大于 2 的偶数都能被 2 整除,所以都不是素数,写 c 语言中判断素数的方法代码的时候经常单独处理这个边界。
问题 2 c 语言中判断素数的方法为什么要优化到平方根
回答 1 c 语言中判断素数的方法如果因数成对出现,一定有一个因数小于等于根号 n,只要根号 n 以内没有因数,c 语言中判断素数的方法就可以确定这个数字是素数,减少循环次数。
问题 3 c 语言中判断素数的方法埃氏筛法适合单个数字判断吗
回答 1 c 语言中判断素数的方法埃氏筛法不适合单独判断一个数字,它是批量筛选区间内全部素数,如果只判断单个数字,优先选用平方根优化试除法。
本文内容仅作为 C 语言素数判断算法学习参考,不同编译器对 math 库链接规则存在差异,实际开发请参考编译器官方文档,本文不对按照本文代码运行产生的编译报错逻辑错误等问题承担相关责任。


