两个素数

Original Link

思想：

• 算术基本定理。
  • 任何一个大于 \(1\) 的自然数 \(N\)，如果 \(N\) 不为质数：
    • 则 \(N\) 可以唯一分解成有限个质数的乘积 \(N=p_1^{a_1}\times p_2^{a_2}\times\cdots\times p_k^{a_k}\)，且最多只有一个大于 \(\sqrt{N}\) 的质因子；
    • 其中 \(p_1 < p_2 < p_3 < \cdots < p_k\) 且均为质数，指数 \(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;
}