数论--合数

将合数进行质因数分解的方式
第一种：试除法；
第二种：Pollard_rho 算法；

第一种
原理：通过预先建立的素数表，遍历素数表将所有的质因数记录并存下来

/*
 *  合数的分解需要先进行素数的筛选
     得到prime[]素数表 
 *  factor[i][0]存放分解的素数
 *  factor[i][1]存放对应素数出现的次数
 *  fatCnt存放合数分解出的素数个数(相同的素数只算一次)
 */
long long factor[100][2];
int fatCnt;
//  合数分解
int getFactors(long long x)
{
    fatCnt = 0;
    long long tmp = x;
    for (int i = 1; prime[i] <= tmp / prime[i]; i++)
    {
        factor[fatCnt][1] = 0;
        if (tmp % prime[i] == 0)
        {
            factor[fatCnt][0] = prime[i];
            while (tmp % prime[i] == 0)
            {
                factor[fatCnt][1]++;
                tmp /= prime[i];
            }
            fatCnt++;
        }
    }
    if (tmp != 1)
    {
        factor[fatCnt][0] = tmp;
        factor[fatCnt++][1] = 1;
    }
    return fatCnt;
}

第二种：
原理：玄学？（没搞懂）
作用：高效的质因数分解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxm=2e5+5;
ll temp[maxm],cnt;//存所有质因子
set<int>st;
//板子:
ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}//求最大公约数 
ll quick_mult(ll a, ll b, ll mod) {
    ll ans = 0;
    while(b) {
        if(b & 1) ans = (ans + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return ans;
}//快速乘法 
ll quick_pow(ll a, ll n, ll mod) {
    ll ans = 1;
    while(n) {
        if(n & 1) ans = quick_mult(ans, a, mod);
        a = quick_mult(a, a, mod);
        n >>= 1;
    }
    return ans;
}//快速幂 
bool miller_rabin(ll n) {
    if(n == 2) return true;
    if(n < 2 || !(n & 1)) return false;
    ll s = 0, d = n - 1;
    while(!(d & 1)) {
        d >>= 1;
        s++;
    }
    for(int i = 1; i <= 11; i++) {
        ll a = rand() % (n - 2) + 2;
        ll now = quick_pow(a, d, n), pre = now;
        for(int j = 1; j <= s; j++) {
            now = quick_mult(now, now, n);
            if(now == 1 && pre != 1 && pre != n - 1) return false;
            pre = now;
        }
        if(now != 1) return false;
    }
    return true;
}//判断n是否为素数 
ll pollard_rho(ll n, int c) {
    ll x, y, i = 1, k = 2;
    x = y = rand() % (n - 2) + 2;
    for( ; ; ) {
        i++;
        x = (quick_mult(x, x, n) + c) % n;
        ll g = gcd(y - x, n);
        if(g > 1 && g < n) return g;
        if(x == y) return n;
        if(i == k) y = x, k <<= 1;
    }
}//求出n的一个因数 c自己写的 玄学的地方  
void find_fac(ll n, int k) {
    if(n == 1) return ;
    if(miller_rabin(n)) {
        st.insert(n);
        temp[n]++;
        return ;
    }
    ll p = n;
    int c = k;
    while(p >= n) p = pollard_rho(p, c--);
    find_fac(p, k);
    find_fac(n / p, k);
}//set里装的是质因数 temp里装的是幂 k和上面的c一样 玄学 
//
int main(){

 ll n;
 cin>>n;
 find_fac(n,107);
 set<int>::iterator it;
for(it=st.begin();it!=st.end();it++)
{
    cout<<*it<<"^"<<temp[*it]<<endl;
}
    return 0;
}