【保姆级教学】判断质数及例题讲解
2026-08-05 19:06:37
发布于：山东
例题
题意
题目让我们判断一个数是否为质数，是的话就输出 Yes，不是的话输出这个数的第二个因数。
解析
鉴于题目要求的 的取值范围不大（），所以可以直接遍历 到 的每一个数字。如果发现其中一个数字可以被 整除，说明 不是质数，那么就直接输出此时的 就可以了。
可以直接输出 的原因：
题目已经说过 也算因数，但是题目要我们输出非质数的第二个因数，也就是除了 以外的最小因子。
而我们判断一个数是否为质数一半是从 开始遍历，所以根本不会遍历到 ! 也就不需要考虑“第二小的因数”！ 我们在遍历中找最小的因数即可！
我们是从小到大遍历的，所以我们程序发现的第一个可以被整除的数就是“第二小的因数”，直接输出即可。这时我们可以用return 0;语句直接结束程序，保证只输出一个数字。
如果从 遍历到 都没有 的因子，那么直接说明 是一个质数！ 我们可以在 for 语句的后面直接写cout << "Yes";，不需要考虑不是质数了情况了——因为如果是合数，前面的 for 语句遍历就直接输出并结束程序了，根本不会完全运行完 for 语句！
标程
#include <bits/stdc++.h> //这个是万能头文件，可以理解为“懒人专属头文件”，可以替代所有的头文件！但是考试不一定让用！要灵活使用哦！
using namespace std; //标准命名空间
int main() //主函数
{
int n; //被判断的数字n
cin >> n; //输入n的值
for(int i = 2;i < n;i++) //判断n是不是质数
{
if(n % i == 0) //如果有可以被n整除的数字，说明n不是质数
{
cout << i; //直接输出i即可
return 0; //这里结束程序！哈哈哈
}
}
cout << "Yes"; //能运行到这里的都是质数
return 0; //哈哈哈哈！结束了！嘻嘻嘻……
}
后记
看到这里说明你真的很有耐心，给你点个赞！不过刚刚标成所示的代码中“判断质数”的部分并不是效率最高的（不过应付这个题目足够了），下面我来讲一下怎么样可以提高效率。
先看标成中的代码：
for(int i = 2;i < n;i++)
{
if(n % i == 0)
{
cout << i;
return 0;
}
}
这里我们发现程序从 运行到 ，时间复杂度为 。但是我们观察一下合数的因子出现的规律：
以 24 为例：
1 2 3 4 6 8 12 24
|
V
1-24 2-12 3-8 4-6
我们总结出：合数的因子是成对出没的！ 那么我们完全不需要一直遍历到 ，只需要遍历到一个值即可，而且这个值小于这个数的 ！
我们再以 36 为例观察一下：
1-36 2-18
3-12 4-9
6
我们得出结论：只需要遍历到 即可！
代码：
for(int i = 2;i <= sqrt(n);i++)
{
if(n % i == 0)
{
cout << i;
return 0;
}
}
注意：这里是 而不是 ，因为 也可能是因子！
到这里，我们成功的把时间复杂度从 降到了
讲解到此结束！感谢各位观众的观看！本文共 2002 字，制作不易，求赞awa~
全部评论 4
- 置顶
[题目传送门](https://htoj.com.cn/cpp/oj/problem/detail?pid=22156387205760) [点击这里可以获得更好的观看效果](https://htoj.com.cn/cpp/oj/problem/detail?pid=22156387205760&tab=2&sid=141719)2026-08-04 来自 山东
1 额，像
注意：这里是 i <= sqrt(n) 而不是 i < sqrt(n)，
这样的也需要用 。然后建议的话
我们可以在 for 语句的后面直接写cout << "Yes";
这种简单的语句还是用文字描述比较好。
2026-08-05 来自 浙江
1
有帮助，赞一个