题目描述
已知正整数n是两个不同的质数的乘积,试求出较大的那个质数。
输入格式
输入只有一行,包含一个正整数n。
输出格式
输出只有一行,包含一个正整数p,即较大的那个质数。
数据范围
6≤n≤2∗10^9
输入样例:
21
输出样例:
7
分析
根据欧几里得-唯一分解定理(见上图)可知无需判断其因数是否为质数
由题意可知n不是质数,是合数,由定理可得n可以唯一分解成有限个质数的乘积,不可能是合数 × 合数或者合数 × 质数,因为这样的话合数又会被分解成质数,分解形式不唯一,与定理矛盾。
代码
#include<iostream>
using namespace std;
int main()
{
int i=1,n;cin>>n;
while(n%++i!=0);
cout<<n/i;
}