从算法到人工智能 · 第 10 课：数论——质数、最大公约数、模运算，程序员的"算术工具箱"

前面几课我们都在跟"数据结构"和"算法套路"较劲。这一课换个口味，聊点纯数学——但别慌，是程序员真正用得上的那部分，叫数论（Number Theory）。

数论听起来高冷，实际上你早就天天在用：密码学的 RSA 加密靠质数，哈希表取模靠余数，加密与随机数生成靠最大公约数。哪怕是 LeetCode 上，也有一大类题直接考质数、公约数、模运算。

这一课的目标：给你一个"算术工具箱"，装进四件最常用的工具——判质数、找质数、求最大公约数、玩转模运算。学完你会发现，很多"看起来很难的数学题"，不过是这几个工具的组合。

一、第一件工具：判断一个数是不是质数

质数：大于 1，且只能被 1 和它自己整除的数。比如 2, 3, 5, 7, 11, 13...。注意 1 不是质数，2 是唯一的偶质数。

最朴素的判断：拿 n 挨个除以 2, 3, 4, ..., n-1，看有没有能整除的。

def is_prime_naive(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

print(is_prime_naive(17))   # True
print(is_prime_naive(18))   # False

这能用，但太慢——判断一个一百万左右的数，要循环一百万次。

关键优化：其实不用除到 n-1，除到 sqrt(n)（平方根） 就够了。为什么？因为如果 n 是合数，一定能拆成 a × b，其中较小的那个因子 a 一定 ≤ sqrt(n)。如果 2 到 sqrt(n) 之间都找不到能整除的数，那 sqrt(n) 之后也绝对找不到。

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:      # 等价于 i <= sqrt(n)
        if n % i == 0:
            return False
        i += 1
    return True

print(is_prime(97))        # True  (97 是质数)
print(is_prime(100))       # False

这里 i * i <= n 就是 i <= sqrt(n) 的写法——避免用浮点的 sqrt，更快也更精确。

复杂度从 O(n) 一下降到了 O(√n)，这是质数判断的"标准答案"。

二、第二件工具：一次性找出所有质数——埃氏筛

有时候你要的不是"判断某一个数"，而是"找出 1 到 N 之间所有质数"。这时候挨个判断太浪费，有个更聪明的办法叫 埃拉托斯特尼筛法（Sieve of Eratosthenes）。

思路像"淘汰赛"：

先假设 2 到 N 全是质数。
从 2 开始，2 是质数，但 2 的所有倍数（4, 6, 8, ...）一定不是质数，划掉。
下一个没被划掉的数是 3，它是质数，划掉 3 的所有倍数（6, 9, 12, ...）。
下一个没被划掉的是 5，划掉它的倍数……依此类推。
最后剩下的，全是质数。

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False       # 0 和 1 不是质数
    i = 2
    while i * i <= n:
        if is_prime[i]:
            # 从 i*i 开始划：更小的倍数早被前面的质数划过了
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
        i += 1
    return [x for x in range(n + 1) if is_prime[x]]

print(sieve(30))   # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

两个细节值得记：

从 i * i 开始划，而不是从 2*i。因为 2*i、3*i 这些更小的倍数，早被更小的质数（2、3）划过了，再划就是重复劳动。
外层循环也到 sqrt(n) 为止（i * i <= n）。

筛法的时间复杂度是 O(n log log n)，在"批量找质数"的场景下，比挨个判断快得多——找一百万以内的质数，毫秒级完成。

三、第三件工具：最大公约数 & 欧几里得算法

最大公约数（GCD, Greatest Common Divisor）：两个数都能整除的最大数。比如 gcd(12, 18) = 6。

最小公倍数（LCM, Least Common Multiple）：两个数都能整除的最小公倍数。比如 lcm(12, 18) = 36。

这两个是一对：它们满足一个漂亮的关系：

gcd(a, b) × lcm(a, b) = a × b

所以求出 GCD，LCM 就顺手出来了：lcm(a, b) = a * b // gcd(a, b)。

那么 GCD 怎么求？古代数学家欧几里得给了个天才算法，辗转相除法（欧几里得算法），核心就一句话：

gcd(a, b) = gcd(b, a % b)，一直辗转，直到余数为 0，此时另一个数就是答案。

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

print(gcd(12, 18))   # 6
print(gcd(1071, 462))  # 21
print(lcm(12, 18))   # 36

拿 gcd(1071, 462) 走一遍，感受它的"辗转"：

gcd(1071, 462)  → 1071 % 462 = 147
gcd(462, 147)   → 462 % 147  = 21
gcd(147, 21)    → 147 % 21   = 0   ← 余数为 0，答案是 21

三步就出结果，根本不用分解质因数。时间复杂度 O(log(min(a,b)))，快得惊人——这也是它两千年来一直是"求 GCD 标准解"的原因。

GCD 的应用多到超乎想象：约分分数、判断两个数是否互质、密码学里的密钥生成、以及下面要讲的模运算。

四、第四件工具：模运算——余数的世界

模运算（modulo） 就是"取余数"，符号 %。a % m 表示 a 除以 m 的余数。

为什么它重要？因为计算机里的整数是有限的（会溢出），而模运算把无穷多的整数"压缩"进 0 ~ m-1 这个有限范围里——哈希表、循环队列、加密、随机数，本质都在跟余数打交道。

模运算有三条"运算律"，是做题的根基（+ * 可以提前取模，结果不变）：

(a + b) % m = ((a % m) + (b % m)) % m
(a × b) % m = ((a % m) × (b % m)) % m
(a - b) % m = ((a % m) - (b % m) + m) % m   ← 减法要 +m 防负数

最经典的应用：大数取模。比如算 2^100 % 7，直接算 2^100 会是个 31 位的大数（而且还没完，指数更大时早就溢出了）。但用模运算律，我们可以在每一步乘完立刻取模，中间结果永远不会超过 m：

def mod_pow(base, exp, m):
    """计算 base^exp % m，不溢出"""
    result = 1
    base %= m
    while exp > 0:
        if exp & 1:                 # 用位运算判断奇偶（第 5 课学过！）
            result = (result * base) % m
        base = (base * base) % m    # 平方，相当于指数翻倍
        exp >>= 1                   # 指数右移，除以 2
    return result

print(mod_pow(2, 100, 7))   # 2^100 % 7 = 2

这叫 快速幂（fast exponentiation），也叫幂取模，时间复杂度从 O(exp) 降到 O(log exp)。它把第 5 课的位运算（& 判奇偶、>> 除以 2）和第 10 课的模运算串了起来——2^100 这个庞然大物，中间每一步都被模运算牢牢压在小范围内，永不溢出。

快速幂是 RSA 加密、区块链、哈希算法的底层零件之一，面试也极爱考。务必吃透。

五、质因数分解：把一个数拆成"质数的积"

每个大于 1 的整数，都能唯一地写成质数的乘积（这叫"算术基本定理"）。比如 60 = 2 × 2 × 3 × 5 = 2² × 3 × 5。

分解的方法很直接：从 2 开始试除，能除尽就记录这个质因子，除到不能再除，再试 3、5……直到 n 变成 1。

def factorize(n):
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:                # 最后剩下的 n 本身是个质因子
        factors.append(n)
    return factors

print(factorize(60))    # [2, 2, 3, 5]
print(factorize(97))    # [97]  （本身是质数）
print(factorize(1))     # []    （1 没有质因子）

注意和"判质数"的呼应：循环条件还是 d * d <= n，因为 n 最多只有一个大于 sqrt(n) 的质因子，最后用 if n > 1 兜住它。

六、复杂度一览：四个工具的"速度"

工具	复杂度	记忆点
判断质数	O(√n)	试除到平方根
埃氏筛（找 1~N 质数）	O(n log log n)	划倍数，从 i² 开始
最大公约数 GCD	O(log min(a,b))	辗转相除
快速幂 mod_pow	O(log exp)	平方翻倍，指数减半

看到没？数论里的高效算法，几乎都是"每次把规模砍半"（GCD 的辗转、快速幂的平方），这跟第 11 课要讲的二分查找是同一个灵魂——对数级的威力。

七、小结

判质数试除到 √n——因为合数必有一个 ≤ √n 的因子。
GCD 用辗转相除 gcd(a,b)=gcd(b,a%b)——三步出结果，LCM 用 a*b//gcd 顺手拿。
模运算让大数不溢出——每一步乘完就 % m，快速幂就是靠这个把指数运算压到 O(log n)。

八、动手实验：三件事亲手敲一遍

实验 1：验证"唯一分解"

每个数的质因数分解是唯一的。写个函数把质因子乘回去，应该得到原数：

def factorize(n):
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

# 验证：把所有质因子乘起来 = 原数
import math
for n in range(2, 1000):
    fs = factorize(n)
    assert math.prod(fs) == n, f"分解错误: {n} -> {fs}"
print("2~999 全部通过：质因子乘积 = 原数")

实验 2：对比"朴素判质数"和"√n 判质数"的速度

import time

def is_prime_slow(n):
    if n < 2: return False
    for i in range(2, n):
        if n % i == 0: return False
    return True

def is_prime_fast(n):
    if n < 2: return False
    i = 2
    while i * i <= n:
        if n % i == 0: return False
        i += 1
    return True

n = 1000003   # 一个一百万左右的质数
t0 = time.time(); r1 = is_prime_slow(n); t1 = time.time()
t2 = time.time(); r2 = is_prime_fast(n); t3 = time.time()
print("朴素:", r1, f"{t1-t0:.4f}秒")
print("√n :", r2, f"{t3-t2:.4f}秒")

你会直观看到：同样的答案，一个要跑半秒，一个几乎瞬间。这就是 O(n) 和 O(√n) 的差距。

实验 3：挑战题——判断两个数是否互质 + 用筛法数质数

互质就是 gcd(a, b) == 1。用刚才的 gcd，统计 1~100 里有多少个数和 100 互质：

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

coprime_count = sum(1 for x in range(1, 101) if gcd(x, 100) == 1)
print("1~100 中与 100 互质的数有", coprime_count, "个")   # 40 个（欧拉函数 φ(100)=40）

这个"与 n 互质的数的个数"就是著名的欧拉函数 φ(n)——它是 RSA 加密的核心之一。你刚算出 φ(100) = 40，等于亲手摸到了现代密码学的一角。

把实验 2 跑一遍，亲眼看朴素算法和 √n 算法的速度差；再把实验 3 的 coprime_count 改成 40 验证一下。数论不是玄学，它是你口袋里最耐用的几件工具——质数、公约数、模运算，从加密到哈希，处处是它们的身影。