题解 | #质数因子#
质数因子
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; }