本文最后更新于 548 天前,其中的信息可能已经有所发展或是发生改变。
思想:
- 算术基本定理。
- 任何一个大于 $1$ 的自然数 $N$,如果 $N$ 不为质数:
- 则 $N$ 可以唯一分解成有限个质数的乘积 $N=p_1^{a_1}\times p_2^{a_2}\dots\times p_i^{a_k}$,且最多只有一个大于 $\sqrt{n}$ 的质因子;
- 其中 $p_1<p_2<p_3\dots p_i$ 且均为质数,指数 $a_k$ 是正整数。
- 由此可知,枚举 $N$ 的最小因子即可。
代码:
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n; cin >> n;
for(int i = 2; i <= n / i; i ++){
if(n % i == 0){
cout << i << ' ' << n / i << endl;
return ;
}
}
}
int main(){
solve();
return 0;
}