P1075 [NOIP 2012 普及组] 质因数分解——题解

解题思路

从 $2$ 开始寻找 $n$ 的最小因数 $p$。由于 $n$ 是两个不同质数的乘积，找到的第一个因数就是较小质数，另一个质数 $n/p$ 必然较大，直接输出。

正确性说明

设两个质因数为 $p<q$。在枚举到 $p$ 前不会找到因数；枚举到 $p$ 时一定整除，输出 $n/p=q$，即较大的质数。

复杂度分析

时间复杂度 $O(\sqrt n)$，空间复杂度 $O(1)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n;cin>>n;
    for(long long p=2;p*p<=n;p++) if(n%p==0){
        cout<<n/p<<'\n';break;
    }
    return 0;
}

#include <bits/stdc++.h> using namespace std; int main(){ long long n;cin>>n; for(long long p=2;p*p<=n;p++) if(n%p==0){ cout<<n/p<<'\n';break; } return 0; }