B站看的:
https://www.bilibili.com/video/BV1TE411p7pW?from=search&seid=14633258382556677371
题目描述
首先是定理:
1、一个数字能被唯一分解成多个质数的乘积(唯一分解定理)。
已知该题的数字n能被分解成两个质数的乘积,则n不能再等于其他几个质数的乘积。
求证,数字n只有1,n和 这两个质数共4个因数。
n=a * b; n=1 * n;
a, b都是质数
1)假设存在其他因数x和y,使得n=xy;且x!=a, y!=b;则x和y有一个是合数,则该合数能继续分解成其他几个质数的乘积,则n等于多个质数连乘的结果,与已知矛盾。
2)假设存在其他因数z,使n=zz,那么z为合数,同1)矛盾。
所以假设不成立。
综述,数字n只有1,n和 这两个质数共4个因数。
即只有遍历俩个数,能得到n= a*b 即能找到答案max(a, b)
为了不超时:
eg: n=8时,有1, 2, 4, 8。 当从小遍历一个因数i时,则较大的因数为n/i即为正确答案。
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
for(int i=2; i<n; i++) // 除开1和本身n
{
if(n%i==0) // i能整除i,则找到了该因数
{
cout << n/i << endl;
break;
}
}
return 0;
}