int multi_mod(int a,int b,int m){
    int ans=0;
    a%=m;
    b%=m;
    while(b){
        if(b&1) {ans+=a;if(ans>m)ans-=m;}
        a<<=1;
        if(a>m)a-=m;
        b>>=1;
    }
    return ans;
}
int power_mod(int a,int b,int m){
    int ans=1;
    a%=m;
    while(b){
        if(b&1){
            ans=multi_mod(ans,a,m);
        }
        a=multi_mod(a,a,m);
        b>>=1;
    }
    return ans;
}
#include <random>
//费马小定理：a^(n-1)=1(mod n)
//n-1=x*(1<<t);
//可能是素数返回true
bool miller_rabin_test(int n,int x,int t){
    static default_random_engine e;
    static uniform_int_distribution<unsigned> u(2,n-2);
    x= power_mod(u(e),x,n);
    if(x==1||x==(n-1)) return true;
    while(--t){
        x=multi_mod(x,x,n);
        if(x==1)break;
        if(x==n-1)return true;
    }
    return false;
}
bool is_prime(int n,int k=5){
    if(n==2||n==3) return true;
    if(n<2||!(n&1)) return false;
    int x=n-1;
    int t=0;
    while((x&1)==0){
        x>>=1;
        ++t;
    }
    for(int i=0;i<k;++i){
        if(!miller_rabin_test(n,x,t)){
            return false;
        }
    }
    return true;
}

这段代码是一种判断一个数是否为素数的算法，通过使用Miller-Rabin测试和费马小定理进行判断。

该算法的大致思路如下：

1. 首先，定义了两个辅助函数multi_mod和power_mod。
2. multi_mod函数用于计算两个数相乘之后对一个数取模的结果。

3. power_mod函数用于计算一个数的幂对一个数取模的结果。

4. 其次，定义了miller_rabin_test函数，用于进行Miller-Rabin测试。

5. Miller-Rabin测试是一种基于费马小定理的素数测试方法。
6. 该函数的参数包括待测试的数n、随机数x和指数幂数t。
7. 首先，通过随机数生成器生成一个范围在[2, n-2]之间的随机数x，然后计算x^t mod n的结果。
8. 如果结果等于1或者等于n-1，则n可能是素数，返回true。
9. 否则，进行t-1次迭代，每次将计算结果进行平方并对n取模，判断是否等于1或者等于n-1。
10. 如果满足条件，返回true；否则，继续迭代。

11. 如果所有迭代都不满足条件，则n可能是合数，返回false。

12. 最后，定义了is_prime函数，用于判断一个数是否为素数。

13. 参数n为待判断的数，参数k为进行Miller-Rabin测试的迭代次数，默认为5次。
14. 首先，判断n是否等于2或者3，若是，则直接返回true。
15. 其次，判断n是否小于2或为偶数（除了2以外的偶数都不可能是素数），若是，则返回false。
16. 然后，通过将n-1进行因式分解，得到一个奇数x和一个偶数t，使得x * (2^t)等于n-1。
17. 接下来，进行k次Miller-Rabin测试。每次测试从区间[2, n-2]中随机选取一个整数x，进行测试。
18. 如果所有测试都通过，则n很可能是素数，返回true。否则，返回false。

#include <cstdlib>
#include <ctime>

int factor[100]{1};
int tol;

int gcd(int a, int b) {
    while (b) {
        a %= b;
        if (!a) return b;
        b %= a;
    }
    return a;
}

int multi_mod(int a, int b, int m) {
    int ans = 0;
    a %= m;
    b %= m;
    while (b) {
        if (b & 1) {
            ans += a;
            if (ans > m) ans -= m;
        }
        a <<= 1;
        if (a > m) a -= m;
        b >>= 1;
    }
    return ans;
}

int power_mod(int a, int b, int m) {
    int ans = 1;
    a %= m;
    while (b) {
        if (b & 1) {
            ans = multi_mod(ans, a, m);
        }
        a = multi_mod(a, a, m);
        b >>= 1;
    }
    return ans;
}

int pollard_rho(int x, int c) {
    int i = 1, k = 2;
    srand(time(0));
    int x0 = rand() % (x - 1) + 1;
    int y = x0;
    while (true) {
        ++i;
        x0 = (multi_mod(x0, x0, x) + c) % x;
        int d = gcd(y - x0, x);
        if (d != 1 && d != x) return d;
        if (y == x0) return x;
        if (i == k) {
            y = x0;
            k <<= 1;
        }
    }
}

void find_fac(int n, int k = 107) {
    if (n == 1) return;
    if (is_prime(n)) {
        factor[++tol] = n;
        return;
    }
    int p = n;
    int c = k;
    while (p >= n) p = pollard_rho(p, c--);
    find_fac(p, k);
    find_fac(n / p, k);
}