分解素数时间复杂度最优解cpp

话不多说，直接上代码

#include<bits/stdc++.h>
using namespace std;
bool isPrime( long num )
{
                 //两个较小数另外处理
                 if(num ==2|| num==3 )
                                 return true ;
                 //不在6的倍数两侧的一定不是质数
                 if(num %6!= 1&&num %6!= 5)
                                 return false ;
                 int tmp =sqrt( num);
                 //在6的倍数两侧的也可能不是质数
                 for(int i= 5;i <=tmp; i+=6 )
                                 if(num %i== 0||num %(i+ 2)==0 )
                                                 return false;
                 //排除所有，剩余的是质数
                 return true ;
}
int printnums(long a){
    if(isPrime(a)){
        cout<<a<<' ';
        return 0;
     }else {
        long i=2;
        for(;i<=sqrt(a);i++){
            if(a%i==0){
                cout<<i<<' ';
                break;
            }
        }
        long b=a/i;
        printnums(b);
        return 0;
    }
}
int main(){
    long a;
    cin>>a;
    printnums(a);
}