题解 | #质数因子#
质数因子
http://www.nowcoder.com/practice/196534628ca6490ebce2e336b47b3607
当一个数x是质数时，符合x=6k+1或者6k-1的规律，不过不是所有符合这个规律的数就是质数 因此在该方法的基础上再结合sqir的方法，来判断是否有质数因子
#include <iostream>
#include <math.h>
using namespace std;
int judge(int i);
int main(){
int x,i=2;
cin>>x;
int temp;
while(x!=1){
temp=judge(x);
x=x/temp;
cout<<temp<<" ";
}
cout<<endl;
return 0;
}
//6k-1,6k,6k+1,6k+2,6k+3,6k+4,其中只有6k-1和6k+1可能是质数
int judge(int a){
if(a%2==0)
return 2;
if(a%3==0)
return 3;
if(a%5==0)
return 5;
int temp=sqrt(a);
for(int i=6;i<=temp;i+=6){
if(a%(i+1)==0)
return i+1;
else if(a%(i-1)==0)
return i-1;
}
return a;
}
查看15道真题和解析