假设你需要统计小于1000万的整数中有多少个素数。最直观的想法是：对每个数逐一判断是否为素数——时间复杂度 $O(n\sqrt{n})$，当数据量达到千万级别时，程序可能需要运行数秒甚至数分钟。但如果换一个思路：用一个布尔数组标记所有合数，剩下的就是素数——时间复杂度骤降至 $O(n \log \log n)$，千万级数据量下只需几十毫秒。

这就是数论算法的魅力：用数学性质替代暴力枚举，将指数级复杂度降为多项式级甚至对数级。在LeetCode中，数论题目往往被归类为"Math"标签，看似简单，实则暗藏玄机。掌握素数筛、GCD、快速幂等核心算法，不仅能让你在面试中游刃有余，更能深刻理解计算机与数学的底层联系。

素数筛：批量找素数的高效方法

判断单个数是否为素数，最简单的方法是试除法：检查从2到 $\sqrt{n}$ 的所有整数是否能整除n。时间复杂度 $O(\sqrt{n})$，对于单个数足够快。但如果需要找出区间 $[1, n]$ 内的所有素数，逐个试除的时间复杂度变成 $O(n\sqrt{n})$，效率极低。

埃拉托斯特尼筛法（埃氏筛） 提供了一个绝妙的思路：与其逐个判断，不如主动"筛掉"合数。从2开始，将每个素数的倍数标记为合数。因为任何合数必然有一个最小的素因子，当我们处理到这个素因子时，该合数就会被标记。

public int countPrimes(int n) {
    if (n <= 2) return 0;
    boolean[] isPrime = new boolean[n];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            // 从i*i开始标记，因为i*2, i*3...已经被更小的素数标记过
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (isPrime[i]) count++;
    }
    return count;
}

时间复杂度为什么是 $O(n \log \log n)$？关键在于内层循环的总次数。对于素数p，我们要标记 $n/p - p + 1 \approx n/p$ 个数。总标记次数约为：

$$n \cdot \sum_{p \le \sqrt{n}} \frac{1}{p}$$

根据素数倒数和的增长规律，这个和约为 $\log \log n$，因此总复杂度为 $O(n \log \log n)$。

埃氏筛算法可视化

图片来源: Wikipedia - Sieve of Eratosthenes

埃氏筛有一个小缺陷：同一个合数可能被多次标记。例如，30会被2标记（作为2的倍数），也会被3标记（作为3的倍数），还会被5标记。欧拉筛（线性筛） 通过确保每个合数只被标记一次，将复杂度优化到真正的 $O(n)$。

核心思想是：让每个合数只被其最小素因子标记。维护一个素数列表，对于每个数i，用已知素数p去标记合数 $i \times p$。如果 $i$ 能被 $p$ 整除，说明 $i \times p$ 的最小素因子不大于 $p$，后续更大的素数就不需要再标记了。

public int countPrimesLinear(int n) {
    if (n <= 2) return 0;
    boolean[] isPrime = new boolean[n];
    int[] primes = new int[n];
    int cnt = 0;
    
    for (int i = 2; i < n; i++) {
        if (!isPrime[i]) primes[cnt++] = i;
        for (int j = 0; j < cnt && i * primes[j] < n; j++) {
            isPrime[i * primes[j]] = true;
            if (i % primes[j] == 0) break; // 关键：保证每个合数只被标记一次
        }
    }
    return cnt;
}

LeetCode 204. Count Primes

这是素数筛最直接的应用。给定整数n，返回小于n的素数个数。

class Solution {
    public int countPrimes(int n) {
        if (n <= 2) return 0;
        boolean[] isPrime = new boolean[n];
        for (int i = 2; i * i < n; i++) {
            if (!isPrime[i]) {
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = true;
                }
            }
        }
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!isPrime[i]) count++;
        }
        return count;
    }
}

复杂度分析：时间复杂度 $O(n \log \log n)$，空间复杂度 $O(n)$。

最大公约数：欧几里得的千年智慧

最大公约数（GCD）是最基础的数论概念。给定两个正整数a和b，GCD(a, b)是能同时整除a和b的最大正整数。两千多年前，欧几里得在《几何原本》中给出了一个优雅的算法：辗转相除法。

核心思想基于一个简单的性质：$\gcd(a, b) = \gcd(b, a \bmod b)$。证明很简单：设 $a = bq + r$（其中 $r = a \bmod b$），任何能整除a和b的数必然能整除r，反之亦然。因此a、b的公约数集合与b、r的公约数集合完全相同。

// 递归写法
public int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 迭代写法
public int gcdIterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

时间复杂度是多少？最坏情况是处理相邻的斐波那契数，此时算法需要 $O(\log(\min(a, b)))$ 次迭代。Lamé定理给出了更精确的估计：迭代次数不超过 $5 \cdot \log_{10}(\min(a, b))$。

最小公倍数（LCM） 可以通过GCD直接计算：$\text{lcm}(a, b) = a \times b / \gcd(a, b)$。注意要先除后乘以避免溢出。

LeetCode 1979. Find Greatest Common Divisor of Array

给定数组nums，返回数组中最小元素与最大元素的最大公约数。

class Solution {
    public int findGCD(int[] nums) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        return gcd(min, max);
    }
    
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

LeetCode 1071. Greatest Common Divisor of Strings

这道题将GCD的概念拓展到字符串。如果字符串t能整除字符串s（即s可以由t重复若干次得到），定义t为s的"因数"。求两个字符串的"最大公约字符串"。

关键观察：如果存在公共因数，那么str1 + str2必须等于str2 + str1。如果这个条件满足，最大公约字符串的长度就是两个字符串长度的GCD。

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        // 如果存在公共因数，拼接顺序不影响结果
        if (!(str1 + str2).equals(str2 + str1)) {
            return "";
        }
        // 最大公约字符串的长度等于两个字符串长度的GCD
        int gcdLen = gcd(str1.length(), str2.length());
        return str1.substring(0, gcdLen);
    }
    
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

LeetCode 365. Water and Jug Problem

经典的水壶问题：两个水壶容量分别为x和y，判断能否准确量出z升水。这是一个纯数学问题，答案是：z必须满足 $z \le x + y$ 且 $z$ 能被 $\gcd(x, y)$ 整除。

数学背景是贝祖定理：对于任意整数a和b，存在整数x和y使得 $ax + by = \gcd(a, b)$。换言之，用两个水壶能倒出的水量恰好是GCD的所有倍数。

class Solution {
    public boolean canMeasureWater(int x, int y, int z) {
        if (z == 0) return true;
        if (z > x + y) return false;
        return z % gcd(x, y) == 0;
    }
    
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

LeetCode 914. X of a Kind in a Deck of Cards

判断一副牌能否分成若干组，每组恰好X张相同的牌。首先统计每种牌的数量，然后求所有数量的GCD。如果GCD >= 2，则存在满足条件的X。

class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        if (deck.length < 2) return false;
        
        // 统计每种牌的数量
        Map<Integer, Integer> count = new HashMap<>();
        for (int card : deck) {
            count.put(card, count.getOrDefault(card, 0) + 1);
        }
        
        // 求所有数量的GCD
        int g = -1;
        for (int c : count.values()) {
            if (g == -1) g = c;
            else g = gcd(g, c);
        }
        
        return g >= 2;
    }
    
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

快速幂：将乘法次数从n降到log n

计算 $a^n$ 最直观的方法是连乘n次，时间复杂度 $O(n)$。但当n很大时（比如 $10^9$ 级别），这种方法显然不可接受。快速幂算法利用指数的二进制表示，将复杂度降到 $O(\log n)$。

核心思想是分治：$a^n = a^{n/2} \cdot a^{n/2}$（n为偶数）或 $a^n = a \cdot a^{(n-1)/2} \cdot a^{(n-1)/2}$（n为奇数）。通过不断将问题规模减半，只需要 $\log n$ 次运算。

// 递归写法
public double myPow(double x, int n) {
    if (n == 0) return 1;
    if (n < 0) {
        return 1 / x * myPow(1 / x, -(n + 1)); // 处理Integer.MIN_VALUE
    }
    double half = myPow(x, n / 2);
    return n % 2 == 0 ? half * half : half * half * x;
}

// 迭代写法（更常用）
public double myPowIterative(double x, int n) {
    long N = n; // 防止溢出
    if (N < 0) {
        x = 1 / x;
        N = -N;
    }
    double result = 1;
    while (N > 0) {
        if (N % 2 == 1) result *= x;
        x *= x;
        N /= 2;
    }
    return result;
}

迭代写法的逻辑是：将n写成二进制，比如 $13 = 1101_2 = 8 + 4 + 1$，则 $a^{13} = a^8 \cdot a^4 \cdot a^1$。遍历n的每一位，如果该位是1，就把对应的 $a^{2^k}$ 乘入结果。

graph LR
    A[计算 a^n] --> B{n是奇数?}
    B -->|是| C[result *= a]
    B -->|否| D[跳过]
    C --> E[a = a * a]
    D --> E
    E --> F[n = n / 2]
    F --> G{n > 0?}
    G -->|是| B
    G -->|否| H[返回result]

LeetCode 50. Pow(x, n)

快速幂的经典应用。注意处理n为负数和Integer.MIN_VALUE的边界情况。

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        double ans = 1;
        while (N > 0) {
            if ((N & 1) == 1) ans *= x;
            x *= x;
            N >>= 1;
        }
        return ans;
    }
}

复杂度分析：时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。

模逆元与费马小定理

在模运算中，快速幂还有一个重要应用：求模逆元。给定整数a和模数m（m为素数），a的模逆元是满足 $a \cdot x \equiv 1 \pmod m$ 的整数x。

根据费马小定理：若m是素数，则 $a^{m-1} \equiv 1 \pmod m$（当 $\gcd(a, m) = 1$）。因此 $a^{m-2} \equiv a^{-1} \pmod m$。用快速幂计算 $a^{m-2} \bmod m$ 即可得到模逆元。

// 求a在模m下的逆元（m为素数）
public long modInverse(long a, long m) {
    return fastPow(a, m - 2, m);
}

public long fastPow(long base, long exp, long mod) {
    long result = 1;
    base %= mod;
    while (exp > 0) {
        if ((exp & 1) == 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

质因数分解：唯一分解定理的应用

算术基本定理指出：任何大于1的整数都可以唯一地分解为素数的乘积。这个定理是质因数分解的理论基础。

最简单的分解方法是试除法：从2开始，逐一尝试能否整除n。如果n能被当前素数整除，就记录这个素因子，并将n除以该素数，直到不能整除为止。优化：只需要尝试到 $\sqrt{n}$ 即可。

public List<Integer> primeFactors(int n) {
    List<Integer> factors = new ArrayList<>();
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            factors.add(i);
            n /= i;
        }
    }
    if (n > 1) factors.add(n); // 剩下的n本身是素数
    return factors;
}

时间复杂度 $O(\sqrt{n})$。如果需要分解大量数，可以先用素数筛预处理所有素数，然后只尝试素数作为除数。

LeetCode 263. Ugly Number

丑数定义：只包含素因子2、3、5的正整数。判断一个数是否为丑数，只需反复除以2、3、5，看最终结果是否为1。

class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) return false;
        int[] factors = {2, 3, 5};
        for (int f : factors) {
            while (n % f == 0) n /= f;
        }
        return n == 1;
    }
}

LeetCode 264. Ugly Number II

找出第n个丑数。这里需要主动生成丑数序列。关键观察：每个丑数都是由更小的丑数乘以2、3或5得到的。使用三个指针分别跟踪乘以2、3、5的位置，每次取最小值作为下一个丑数。

class Solution {
    public int nthUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;
        
        for (int i = 1; i < n; i++) {
            int next2 = ugly[p2] * 2;
            int next3 = ugly[p3] * 3;
            int next5 = ugly[p5] * 5;
            ugly[i] = Math.min(next2, Math.min(next3, next5));
            
            if (ugly[i] == next2) p2++;
            if (ugly[i] == next3) p3++;
            if (ugly[i] == next5) p5++;
        }
        return ugly[n - 1];
    }
}

复杂度分析：时间复杂度 $O(n)$，空间复杂度 $O(n)$。

组合数学与模运算

在LeetCode中，组合数学问题通常需要计算组合数 $C(n, k)$ 或排列数 $P(n, k)$，结果往往需要对某个大素数取模。

组合数公式：

$$C(n, k) = \frac{n!}{k!(n-k)!} = \frac{n \cdot (n-1) \cdot \ldots \cdot (n-k+1)}{k!}$$

在模运算下，除法需要转化为乘以模逆元：

$$C(n, k) \bmod p = n! \cdot (k!)^{-1} \cdot ((n-k)!)^{-1} \bmod p$$
// 预计算阶乘和阶乘的模逆元
long[] fact = new long[MAX];
long[] invFact = new long[MAX];
long MOD = 1_000_000_007;

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAX; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    invFact[MAX-1] = fastPow(fact[MAX-1], MOD - 2, MOD);
    for (int i = MAX - 2; i >= 0; i--) {
        invFact[i] = invFact[i+1] * (i+1) % MOD;
    }
}

long combination(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invFact[k] % MOD * invFact[n-k] % MOD;
}

题目总结

题目 核心算法 难度
204. Count Primes 埃氏筛 中等
263. Ugly Number 质因数分解 简单
264. Ugly Number II 多指针 + 数学推导 中等
50. Pow(x, n) 快速幂 中等
1979. Find GCD of Array GCD 简单
1071. GCD of Strings GCD性质 简单
365. Water and Jug Problem 贝祖定理 中等
914. X of a Kind in a Deck GCD应用 简单

写在最后

数论算法的魅力在于：简单的数学性质能带来巨大的效率提升。素数筛将 $O(n\sqrt{n})$ 降到 $O(n \log \log n)$，快速幂将 $O(n)$ 降到 $O(\log n)$，这些优化在竞赛和工程中都有着广泛的应用。

掌握这些算法，需要理解其背后的数学原理，而不仅仅是记忆代码模板。欧几里得算法的本质是等价类划分，快速幂的本质是二进制分解，素数筛的本质是合数的传递性。当你理解了这些本质，面对变体题目时才能游刃有余。

参考资料

  1. Sieve of Eratosthenes - Wikipedia
  2. Binary Exponentiation - CP-Algorithms
  3. Euclidean Algorithm - GeeksforGeeks
  4. Integer Factorization - CP-Algorithms
  5. Modular Multiplicative Inverse - CP-Algorithms
  6. Fermat’s Little Theorem - Brilliant
  7. Number Theory Topics - LeetCode Discuss
  8. Ugly Number Summary - Labuladong