题解 | #质数因子#

//在19年的钉子大佬的c++题解基础上做了改进，运行4ms，不超时
#include <iostream>
#include<cmath>

using namespace std;
int main() {
    long n;
    while (cin>>n) {
        long ori=sqrt(n);
        while(n!=1){
            while(n%2==0){
                    n/=2;
                    cout<<2<<' ';
                }
            for(int i=3;i<=n;){//讨论中很多人说应该在for这里把n改成sqrt（n），这是不对的
                if(i>ori){//改进2：判断当除数已经超过原始数据的平方根之后，此时剩下的被除数一定是个素数，直接输出并跳出循环，解决了大素因子导致的超时问题
                    cout<<n;
                    n=1;
                    break;
                }
                while(n%i==0){
                    n/=i;
                    cout<<i<<' ';
                }
                i=i+2;//改进1:2之后的素数可以每次+2递增  
            }
        } 
    }
    return 0;
}