题解 | #质数因子#

质数因子

https://www.nowcoder.com/practice/196534628ca6490ebce2e336b47b3607

//在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;
}

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务