注意题目给出的n是两个不同质数的乘积,所以只要从小到大遍历找出第一个质数,再用原数除以第一个质数就得到了较大的质数。
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
for (int i = 2; ; i ++ )
if (n % i == 0)
{
cout << n / i << endl;
break;
}
return 0;
}
若是求任意数质因数分解后的最大质数,可用以下方法:
#include <iostream>
#include <vector>
using namespace std;
vector<int> primes; //变长数组用来存n的质数
int main()
{
int n;
cin >> n;
for (int i = 2; i <= n / i; i ++ ) //从2开始遍历,将n的每个质数从小到大储存
{
if (n % i == 0)
{
primes.push_back(i);
while (n % i == 0) n/= i; //把相同的质因数反复除尽,例如100质因数分解中有2,除以2得50
} //50质因数分解仍然有2,再除2的25, 25中就没有2了
}
if (n > 1) primes.push_back(n); //分解完毕后,最终剩下的还是质数,再push进去。
//例如17,分解为2和5后,还剩7,为最大质因数
cout << primes.back() << endl; //数组中最后一个数一定是最大质因数
return 0;
}