思路很简单，就是用n除以从2开始的数（把这个数设为i)，如果除的尽，那么i就是n的一个质因数，
然后用n/=i，如果此时n<i那么直接结束循环，否则把i赋为2重复这一过程（每一次循环都能找出最小的那个质因数）
当然如过n是一个很大的质数，复杂度还是会退化到O(n)
所以我们每次都要判断一下n是不是一个素数
代码：
#include<bits/stdc++.h>
using namespace std;
bool is_prime(long long x){
if(x==1)
return false;
if(x==2||x==3)
return true;
if(x%6!=1&&x%6!=5)
return false;
int s=sqrt(x);
for(int i=5;i<=s;i+=6)
if(x%i==0||x%(i+2)==0)
return false;
return true;
}
vector<long long> pfc(long long n){//快速质因数分解
vector <long long> st;
long long i=0;
if(n==1)
{
st.push_back(1);
return st;
}
while(i<n)
{
if(is_prime(n)){
st.push_back(n);
return st;
}
for(i=2;i<n;i++)
{
if(n%i==0)
{
st.push_back(i);
n/=i;
break;
}
}
}
st.push_back(n);
return st;
}
原文：https://www.cnblogs.com/EdwardZhang/p/10713124.html