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

知识点

质因数分解、试除法、整数运算

解题思路

从2开始枚举因子i，第一次能整除n时，输出n/i。题目保证n是两个不同质数的乘积。

正确性说明

由于只有两个质因子，较小质因子一定不超过sqrt(n)，也一定是从2开始找到的第一个非平凡因子；除法得到另一个、也就是较大的质因子。

易错点

本题依赖两个不同质数乘积的保证；不是输出最小因子；用i*i<=n判断时使用long long。

复杂度

时间O(sqrt(n))，空间O(1)。

参考代码（GNU C++17）

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