题解 | 质数因子

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
    int a;
    cin>>a;
    int p=2;
    while(p<=sqrt(a)){
        if(a%p==0){
            a=a/p;
            cout<<p<<" ";
        }
        else p++;
    }
    cout<<a<<endl;
    
    
}

看似困难实际代码很简答的一道题，考验小学数学能力，很羞愧解题思路还是文心一言帮我想到的。一开始陷入怎么确定是哪个质数这样的思路里，后来想到只要逐步加+1去，如果能被后面的数整除，那么一定早已被前面的质数整除了。题目并没有规定使用怎样的顺序去整除，具体思路：

从最小的质数2开始，循环整除。如果不能整除，则+1；

空间优化，如果存在大于根号N的因子，那么一定有对应的小于根号N的因子，因此累加到小于根号N即可，除剩下的n就是最后一个因子。