【题目来源】
洛谷：P1075 [NOIP 2012 普及组] 质因数分解 - 洛谷 (luogu.com.cn)
【题目描述】
已知正整数 \(n\) 是两个不同的质数的乘积，试求出两者中较大的那个质数。
【输入】
输入一个正整数 \(n\)。
【输出】
输出一个正整数 \(p\)，即较大的那个质数。
【输入样例】
21
【输出样例】
7
【算法标签】
《洛谷 P1075 质因数分解》 #数学# #素数判断,质数,筛法# #NOIP普及组# #2012#
【代码详解】
#include <bits/stdc++.h> // 包含标准库头文件
using namespace std;// 判断素数的辅助函数
bool fun(int n) {if (n <= 1) return false; // 1和负数不是素数for (int i = 2; i < sqrt(n); i++) { // 只需检查到√n的范围if (n % i == 0) return false; // 发现能整除的因子}return true; // 未发现因子则是素数
}int main() {int n; // 存储输入的正整数cin >> n; // 读取输入// 遍历2到n寻找满足条件的因子for (int i = 2; i <= n; i++) {if (n % i == 0) { // 如果i是n的因子// 检查i和n/i是否都是素数if (fun(i) && fun(n / i)) {cout << n / i; // 输出较大的素数因子break; // 找到后立即退出循环}}}return 0; // 程序正常结束
}
【运行结果】
21
7