本文最后更新于 705 天前,其中的信息可能已经有所发展或是发生改变。
Original Link
思想:
- 算术基本定理。
- 任何一个大于 1 的自然数 N,如果 N 不为质数:
- 则 N 可以唯一分解成有限个质数的乘积 N=p1a1×p2a2⋯×piak,且最多只有一个大于 n 的质因子;
- 其中 p1<p2<p3…pi 且均为质数,指数 ak 是正整数。
- 由此可知,枚举 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; |
| } |