大整数分解

What · 是什么

整数分解（Integer Factorization）：把正整数 n 写成质因子乘积 n=∏p_i^{e_i}。基础算法是试除法（枚举 2..√n，O(√n)，配合素数表 O(√n/ln n)）；大整数（>1e14）用 Pollard-Rho + Miller-Rabin 组合（期望 O(n^{1/4})）。分解结果可进一步求：约数个数 τ(n)=∏(e_i+1)、约数和、枚举全部约数（DFS 组合因子幂）。分解是数论题的前置工具（约数类、RSA 类、公因数类）。Python 内建大整数便于实现 Pollard-Rho；1e12 内试除法+素数表足够。

Why · 为什么

How · 实现

伪代码

def trial_division(n):
  res = []
  d = 2
  while d*d <= n:
    while n % d == 0: res.append(d); n //= d
    d += 1
  if n > 1: res.append(n)
  return res
# 素数表版
def trial_division_primes(n, primes):
  res = []
  for p in primes:
    if p*p > n: break
    while n % p == 0: res.append(p); n //= p
  if n > 1: res.append(n)
  return res
# 约数个数
def divisor_count(factors):
  from collections import Counter
  r = 1
  for e in Counter(factors).values(): r *= (e+1)
  return r
# 大数: factor(n) 见 pollard-rho 节点

Python 实现

from math import isqrt
from collections import Counter


def trial_division(n):
    """试除法分解: O(sqrt(n)). 适用于 n <= 1e7 左右."""
    res = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            res.append(d)
            n //= d
        d += 1
    if n > 1:
        res.append(n)
    return res


def trial_division_primes(n, primes):
    """带素数表的试除: O(sqrt(n)/ln n)."""
    res = []
    for p in primes:
        if p * p > n:
            break
        while n % p == 0:
            res.append(p)
            n //= p
    if n > 1:
        res.append(n)
    return res


def sieve_primes(limit):
    is_p = [True] * (limit + 1)
    is_p[0] = is_p[1] = False
    for i in range(2, isqrt(limit) + 1):
        if is_p[i]:
            for j in range(i * i, limit + 1, i):
                is_p[j] = False
    return [i for i in range(2, limit + 1) if is_p[i]]


def divisor_count_from_factors(factors):
    """由质因子列表求约数个数."""
    c = Counter(factors)
    res = 1
    for e in c.values():
        res *= (e + 1)
    return res


def divisors_from_factors(factors):
    """枚举全部约数 (升序)."""
    c = Counter(factors)
    res = [1]
    for p, e in c.items():
        cur = []
        pe = 1
        for _ in range(e + 1):
            for x in res:
                cur.append(x * pe)
            pe *= p
        res = cur
    return sorted(res)


if __name__ == "__main__":
    import random
    random.seed(6)

    def trial_factor(x):
        res = []
        d = 2
        while d * d <= x:
            while x % d == 0:
                res.append(d); x //= d
            d += 1
        if x > 1: res.append(x)
        return res

    # 试除法正确性
    for _ in range(500):
        n = random.randint(2, 10**6)
        assert trial_division(n) == trial_factor(n), n
    assert trial_division(360) == [2, 2, 2, 3, 3, 5]
    assert trial_division(1) == []
    assert divisor_count_from_factors(trial_division(360)) == 24   # 2^3*3^2*5 -> 4*3*2=24
    dvs = divisors_from_factors(trial_division(360))
    assert len(dvs) == 24 and sum(1 for x in range(1, 361) if 360 % x == 0) == 24
    assert sorted(x for x in range(1, 361) if 360 % x == 0) == dvs

    # 素数表试除
    primes = sieve_primes(10000)
    for _ in range(200):
        n = random.randint(2, 10**8)
        assert trial_division_primes(n, primes) == trial_factor(n), n
    print("integer-factorization: all tests passed")

易错点

• 试除到 i*i<=n 用 int 截断导致溢出（Python 无此问题但浮点 sqrt 有误差）
• 素数表试除时没在 p*p>n 处 break，浪费且可能越界
• 分解完 n 剩余 >1 忘加入结果（它就是最后一个质因子）
• Pollard-Rho 对素性判断缺失死循环
• 约数计数把指数直接相乘而非 (e+1)
• 结果未排序/去重导致比较与预期不一致

例题

信源

• CP-Algorithms✓ https://cp-algorithms.com/algebra/factorization.html
• OI Wiki✓ https://oi-wiki.org/math/number-theory/pollard-rho/
• article✓ https://en.wikipedia.org/wiki/Integer_factorization