数学必刷8题：素数、进制与数学建模

引言

数学题是面试中的「分水岭」：会的人三分钟秒杀，不会的人想破头。但 LeetCode 的数学题有很强的套路性——绝大多数逃不出这几类：素数筛选、进制与取模、快速幂、GCD/LCM、数学推导（排列组合、求和公式）。

本文精选 8 道必刷数学题，每题给出「数学建模 → 代码实现 → 面试常问的 follow-up」，帮你把数学题从「玄学」变成「套路」。

前置：基本循环与递归。位运算相关的数学题见 /leetcode-bit-manipulation-problems/。

目录

• 1. 数学题的题型地图
• 2. 计数质数（LeetCode 204）— 埃氏筛
• 3. 快乐数（LeetCode 202）— 循环检测
• 4. 回文数（LeetCode 9）— 反转一半
• 5. 进制转换（LeetCode 168）— 取模与整除
• 6. Pow(x, n)（LeetCode 50）— 快速幂
• 7. 最大公约数（LeetCode 1071/243）— 辗转相除
• 8. 阶乘后的零（LeetCode 172）— 数论推导
• 9. 数学题速查表
• 延伸阅读

1. 数学题的题型地图

记忆：数学题 = 数论套路 + 边界处理（溢出、负数、0）。

2. 计数质数（LeetCode 204）— 埃氏筛

问题：统计小于 n 的质数个数。

埃氏筛思想：从 2 开始，把每个质数的倍数全部标记为合数。筛完没被标记的就是质数。

def count_primes(n):
    if n < 3:
        return 0
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    i = 2
    while i * i < n:                 # 只需筛到 sqrt(n)
        if is_prime[i]:
            for j in range(i * i, n, i):   # 从 i*i 开始（避免重复标记）
                is_prime[j] = False
        i += 1
    return sum(is_prime)

复杂度：O(n log log n)，接近线性。面试常问「为什么从 i*i 开始」——因为小于 i² 的 i 的倍数已被更小的质数标记过。

3. 快乐数（LeetCode 202）— 循环检测

问题：反复将数字替换为各位数字平方和，判断能否变成 1。

数学事实：非快乐数最终会进入循环（要么撞到 4，要么进入一个周期）。所以用快慢指针或 HashSet 检测循环。

def is_happy(n):
    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        n = sum(int(d) ** 2 for d in str(n))
    return n == 1

follow-up：为什么一定会有循环？因为对一个位数固定的数，平方和是有界的（如 999 → 243），状态空间有限 → 必然撞到重复 → 要么 1 要么循环。

4. 回文数（LeetCode 9）— 反转一半

问题：判断整数是否为回文，不转成字符串。

思路：反转后半部分数字，与前半部分比较。负数直接排除，末尾为 0 的非 0 数排除。

def is_palindrome(x):
    if x < 0 or (x % 10 == 0 and x != 0):
        return False
    rev = 0
    while x > rev:
        rev = rev * 10 + x % 10
        x //= 10
    return x == rev or x == rev // 10   # 奇数位时 rev 多一位

要点：反转一半（不是全部）避免溢出。1221 → x=12, rev=12 相等；121 → x=1, rev=12，rev//10=1 相等。

5. 进制转换（LeetCode 168）— 取模与整除

问题：将正整数转换为 Excel 列名（1→A，26→Z，27→AA）。

思路：这是「1-indexed 的 26 进制」——和普通 26 进制不同，n % 26 == 0 时要借位（n -= 1）。

def convert_to_title(column_number):
    result = []
    while column_number > 0:
        column_number -= 1              # 1-indexed 转 0-indexed（关键！）
        result.append(chr(column_number % 26 + ord('A')))
        column_number //= 26
    return ''.join(reversed(result))

为什么 n -= 1：普通进制 0..25，这里 1..26。26 本应映射 Z（25），但 26 % 26 == 0 会得 A——先减 1 让取模正确。

6. Pow(x, n)（LeetCode 50）— 快速幂

问题：实现 pow(x, n)，n 可为负，要求 O(log n)。

快速幂思想：x^n = (x²)^(n/2)，每次把指数减半，底数平方。n 为负时转为 1 / pow(x, -n)（注意 -2³¹ 溢出用 long）。

def my_pow(x, n):
    def quick(x, n):
        if n == 0:
            return 1.0
        half = quick(x, n // 2)
        if n % 2 == 0:
            return half * half
        return half * half * x

    if n < 0:
        x = 1 / x
        n = -n
    return quick(x, n)

迭代版（更省栈）：

def my_pow_iter(x, n):
    if n < 0:
        x, n = 1 / x, -n
    result = 1.0
    while n:
        if n & 1:           # 当前位为 1
            result *= x
        x *= x              # 底数平方
        n >>= 1
    return result

要点：快速幂 = 二分的幂，可推广到「矩阵快速幂」（斐波那契）、模幂（RSA 需要）。

7. 最大公约数（LeetCode 1071/243）— 辗转相除

问题：求两个数的最大公约数，用于字符串的最大公因子等题。

辗转相除：gcd(a, b) = gcd(b, a % b)，直到余数为 0。

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

扩展用途：

• 字符串最大公因子（LeetCode 1071）：str1 + str2 == str2 + str1 时才存在公因子，长度取 gcd。
• LCM：lcm = a * b // gcd(a, b)。
• 裴蜀定理：gcd 是 a、b 线性组合的最小正整数。

8. 阶乘后的零（LeetCode 172）— 数论推导

问题：n! 末尾有多少个 0。

推导：末尾的 0 = 10 的个数 = min(因子2个数, 因子5个数)。因为 2 的个数远多于 5，所以 0 的个数 = n! 中因子 5 的个数。

def trailing_zeroes(n):
    count = 0
    while n:
        n //= 5
        count += n
    return count

为什么是 n//5 + n//25 + n//125…：5、25、125 各贡献一个、两个、三个 5 因子，累加即得。25! 有 5 + 1 = 6 个 0。

9. 数学题速查表

延伸阅读

• /leetcode-bit-manipulation-problems/ — 位运算数学题：异或、2 的幂、汉明重量
• /leetcode-backtracking-problems/ — 数学与搜索结合（如数独）
• LeetCode 数学标签 — 完整题库