整数分解（因数分解）

给出一个正整数，将其写成几个素数的成就，这个过程就叫整数分解，也叫因数分解。

例如：$15=3\times5$，$8=2\times 2\times 2$，$20=2\times 2\times 5$。

下面介绍三种整数分解的方法：

1. 应用试除法对正整数 n 进行分解
2. 筛选法对整数分解
3. Pollard rho 整数分解方法

1. 应用试除法对正整数 n 进行分解

令 $m=n$，从 $2$ ~ $n$一一枚举，如果当前数能够整除 $m$，那么当前数就是 $n$ 的素数因子，并用整数 $m$ 将当前数除尽为止。

若循环结束后 $m$ 是大于 $1$ 的整数，那么此时 $m$ 也是 $n$ 的素数因子。代码：

const int N = 100005;
int factor[N], cnt;	// 素因子和素因子的数目，下标从 1 开始
void divide(int n)
{
    cnt = 0;
    for (int i = 2; i * i <= n; ++i)    // i <= sqrt(double(n))
        while (n % i == 0)
        {
            factor[++cnt] = i;
            n /= i;
        }
    if (n != 1)
        factor[++cnt] = n;
}

例：HDU 1164 - Eddy’s research I

给你一个数，把它写成素因子相乘的形式。例如输入 9412，输出 2*2*13*181，代码如下：

#include <iostream>
using namespace std;
const int N = 65536;
int factor[N], cnt;	// 素因子和素因子的数目，下标从 1 开始
void divide(int n)
{
    cnt = 0;
    for (int i = 2; i * i <= n; ++i)    // i <= sqrt(double(n))
        while (n % i == 0)
        {
            factor[++cnt] = i;
            n /= i;
        }
    if (n != 1)
        factor[++cnt] = n;
}
int main(void)
{
    int x;
    while (cin >> x)
    {
        divide(x);
        for (int i = 1; i <= cnt; ++i)
            cout << factor[i] << "*\n"[i == cnt];
    }
    return 0;
}

2. 筛选法对整数分解

上面的试除法，对不大于 $\sqrt n$ 的每一个数都试了一遍，但是事实上，我们只要试那些不大于 $\sqrt n$ 的素数就行了，所以我们先做个素数筛，然后再依据素数筛去找 $n$ 的素因子，会大大减少程序的运行时间。

还是上面的那道题，我们用筛选法对整数分解，再做一次。代码：

#include <iostream>
using namespace std;
const int N = 65536;
bool isprime[N];
int prime[N], nprime;
int factor[N], cnt;	// 素因子和素因子的数目，下标从 1 开始
void doprime(void)
{
    nprime = 0;
    for (int i = 0; i < N; ++i)
        isprime[i] = 1;
    for (int i = 2; i < N; ++i)
    {
        if (isprime[i] == 1)
            prime[++nprime] = i;
        for (int j = 1; j <= nprime && prime[j] * i < N; ++j)
        {
            isprime[prime[j] * i] = 0;
            if (i % prime[j] == 0)
                break;
        }
    }
}
void divide(int n)
{
    cnt = 0;
    for (int i = 1; i <= nprime && prime[i] * prime[i] <= n; ++i)    // i <= sqrt(double(n))
        while (n % prime[i] == 0)
        {
            factor[++cnt] = prime[i];
            n /= prime[i];
        }
    if (n != 1)
        factor[++cnt] = n;
}
int main(void)
{
    doprime();
    int x;
    while (cin >> x)
    {
        divide(x);
        for (int i = 1; i <= cnt; ++i)
            cout << factor[i] << "*\n"[i == cnt];
    }
    return 0;
}

3. Pollard rho 整数分解方法

如果要对比较大的整数分解，显然以上两种方法都失去了实用价值。下面介绍 Pollard rho 整数分解方法。

算法原理：

生成两个整数 $a$ 和 $b$，计算 $p=gcd(a-b,n)$，直到 $p$ 不为 $1$ 或 $a,b$ 出现循环为止，若 $p=n$，则 $n$ 为质数，否则 $p$ 为 $n$ 的一个约数。选取一个小的随机数 $x1$，迭代生成 $x_i=x{i-1}^2+k$，一般取 $k=1$，若序列出现循环，则退出。计算 $p=gcd(x_{i-1}-x_i,n)$，若 $p=1$，返回上一步，直到 $p\gt 1 $为止；若 $p=n$，则 $n$ 为素数，否贼 $p$ 为 $n$ 的一个约数并递归分解 $p$ 和 $n/p$。

算法实现：

代码中 gcd() 和 miller_rabin() 等未在本篇博客定义的函数分别参考欧几里得和Miller-Rabin素数测试，这里就不再重复贴那些代码了。

typedef long long ll;
const int N = 1000;
ll factor[N], cnt;	// 素因子和素因子的数目，下标从 1 开始
ll mini;
ll pollard_rho(ll n, int c)
{
    ll x, y, d, i = 1, k = 2;
    x = random(n - 1) + 1;
    y = x;
    while (true)
    {
        ++i;
        x = (multi(x, x, n) + c) % n;
        d = gcd(y - x, n);
        if (1 < d && d < n)
            return d;
        if (y == x)
         	return n;
        if (i == k)
        {
            y = x;
            k <<= 1;
		}
    }
}
void find(ll n, int k)
{
    if (n == 1)
        return ;
    if (miller_rabin(n))
    {
        factor[++cnt] = n;
		mini = min(n, mini);
        return ;
    }
    ll p = n;
    while (p >= n)
        p = pollard_rho(p, k--);
    find(p, k);
    find(n / p, k);
}

例题：POJ 1811 - Prime Test

给你一个数 $N$ $(2\leqslant N\leqslant 2^{54})$ 判断 $N$是否为素数，是的话直接输出 “prime”，不是的话输出最小质因数。

例题题解：Prime Test（Miller-Rabin素数测试+Pollard rho整数分解）