CSP/信奥赛C++语法基础刷题训练（22）：洛谷P1075：[NOIP2012 普及组] 质因数分解

题目描述

已知正整数 $n$ 是两个不同的质数的乘积，试求出两者中较大的那个质数。

输入格式

输入一个正整数 $n$。

输出格式

输出一个正整数 $p$，即较大的那个质数。

样例 #1

样例输入 #1

21

样例输出 #1

7

提示

$1\le n\le 2\times 10^9$

NOIP 2012 普及组 第一题

AC代码

#include<bits/stdc++.h>
using namespace std;
/*思路： 
按题意模拟：i是质数，且n/i是质数，且n能整除i 
*/
int n; 
bool isPrime(int x){if(x<=1) return false;for(int i=2;i<=sqrt(x);i++){if(x%i==0) return false;}return true;
}
int main(){cin>>n;for(int i=2;i<=sqrt(n);i++){//只在因子对较小的范围找，提升算法效率 if(isPrime(i) && isPrime(n/i) &&n%i==0){//找到较小的 cout<<n/i;//输出较大的 break;}}return 0;
}

文末彩蛋：

点击王老师青少年编程主页有更多精彩内容