题解 | #质数因子#

当一个数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;
    
}