数学概念速查：素数 / 对数 / 离散数学

前置：这篇写于 2019 年 10 月。我当时在梳理"程序员应该重新捡起来的数学基础"，从散落的笔记里挑出 3 个常被问到、却总记不清的：素数（Prime）、对数（Logarithm）、离散数学（Discrete Math）。本文以"概念 + 代码 + 关联"三层结构呈现。

为什么写这篇

工作 5 年之后，我发现自己读 RFC、看算法书、甚至 review 同事的代码时，常常被一个数学概念卡住 5 分钟——不是不会，是太久没用了，定义都模糊了。

举 3 个真实例子：

• 同事写的"质数判定"用了 n/2 遍历，我一眼看出应该用 sqrt(n)，但嘴上说不清"为什么遍历到 sqrt 就够"
• 看到数据库索引 O(log n) 的描述，我脑子里浮现的是"log 不是很大吗"——把"以 10 为底"和"以 2 为底"搞混了
• 看到 Redis Cluster 的"16384 个 slot"用 CRC16 取模，我能跟着算，但说不出"为什么是 16384"

这 3 个例子背后分别站着 素数、对数、离散数学。于是我决定写一篇"自己的速查手册"。

3 个概念速查

1. 素数（Prime / 质数）

定义：在大于 1 的自然数中，除了 1 和它自身外，无法被其他自然数整除的数，否则称为合数（Composite）。

素数序列：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ...

判断定理：若 n 是合数，则 n 必有一个小于等于 sqrt(n) 的因子。 因此遍历到 sqrt(n) 即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import math

def is_prime(n: int) -> bool:
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    # 只遍历到 sqrt(n)，步长 2（跳过偶数）
    for i in range(3, int(math.isqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

Eratosthenes 筛法：求 n 以内所有素数的 O(n log log n) 算法。

1
2
3
4
5
6
7
8

def sieve(n: int) -> list[bool]:
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    return is_prime

程序员视角的素数用途：

2. 对数（Logarithm）

定义：如果 a 的 x 次方等于 N（其中 a > 0 且 a ≠ 1），那么数 x 叫做以 a 为底 N 的对数（logarithm），记作 x = logₐN。其中 a 叫做底数（base），N 叫做真数（argument）。

等价关系：a^x = N ⟺ x = logₐN

对数恒等式（程序员最常用的几个）：

2 个最常见的底数：

• lg N = log₂N：以 2 为底，计算机科学默认底数（信息论、二叉树、二分查找）
• ln N = logₑN（自然对数）：以 e（≈ 2.71828）为底，微积分、复利、机器学习 大量出现

计算机科学的时间复杂度速查：

Python 代码示例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import math

math.log(8, 2)        # 3.0  →  log₂8 = 3
math.log(100, 10)     # 2.0  →  log₁₀0 = 2
math.log2(1024)       # 10.0 →  2^10 = 1024
math.log(math.e)      # 1.0  →  ln(e) = 1

# 时间复杂度直觉：n=100 万
n = 1_000_000
print(math.log2(n))   # ≈ 19.93  → 二分查找仅需 20 次
print(n * math.log2(n))  # ≈ 2e7  → nlogn 排序

3. 离散数学（Discrete Mathematics）

定义：研究离散量（discrete quantities）的结构及其相互关系的数学学科，是现代数学的一个重要分支。与连续数学（微积分、实分析）相对，离散数学的对象一般是有限个或可数个元素。

为什么计算机专业必修： “通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力。"（任一本离散数学教材的绪论）

应用领域：程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础。

四大支柱（“集合、图、代数、逻辑”）：

集合论部分详解（最容易和 SQL 关联）：

• 集合及其运算：并（UNION）、交（INTERSECT）、差（EXCEPT）、补、对称差（A △ B）
• 二元关系与函数：映射、单射、满射、双射——这 3 个"射"是后续理解 hash、索引、SQL 关联的基础
• 自然数及自然数集：Peano 公理（5 条），不靠"自然数就是 0, 1, 2…“这种直觉
• 集合的基数：可数集 vs 不可数集；Hilbert 旅馆问题

图论部分详解（最容易和算法关联）：

• 图的基本概念：顶点（V）、边（E）、度（degree）、路径、连通性
• 欧拉图 vs 哈密顿图：前者"走遍所有边一次”（一笔画问题，源自 Königsberg 七桥问题），后者"走遍所有顶点一次”（TSP 旅行商问题）
• 树：特殊的无环连通图；二叉树、B 树、红黑树都属此家族
• 图的矩阵表示：邻接矩阵（O(1) 查边、空间 O(V²)）、关联矩阵、邻接表（O(deg) 查边、空间 O(V+E)）
• 图着色：相邻顶点不能同色——编译器寄存器分配、时间表排课本质都是图着色
• 带权图：边上带权值——Dijkstra 最短路径、Prim 最小生成树

三个概念的内在关联

如果一定要给"程序员应该理解这三个概念"找一个理由，那就是：

1. 素数 = “不可分解的最小单位"——是密码学和 hash 算法的基石
2. 对数 = “乘除变加减、规模变线性"——是时间复杂度的描述语言
3. 离散数学 = “有限世界的全套工具箱"——是计算机科学本身的母语

三者加起来，构成了计算机从业者的"数学底盘”。

5 个常见误区

1. “素数 = 质数 = 是不是 1”：1 既不是素数也不是合数（1 只有 1 个因子，素数要求 2 个因子）
2. “log 默认以 10 为底”：数学书以 10 为底（lg），计算机科学以 2 为底（log₂），微积分以 e 为底（ln），三个底数别混
3. “O(log n) 比 O(1) 慢很多”：错。log₂(10亿) ≈ 30，所以 O(log n) 在工程上几乎等同于 O(1)（常数 30）
4. “离散数学 = 离散事件数学”：错。“离散"指离散量（可数/有限），对应的是连续量（微积分处理的实数连续区间）
5. “对数 = 减法”：对数是乘除转加减，不是减法本身

写在最后

这一篇没有"实战代码”，更多是给自己打地基。我后来每次被数学概念卡住，都会回到这篇过一遍——素数定义 → Eratosthenes 筛法 → 对数换底 → 图论七大概念，3 分钟过完，思路立刻清晰。

如果你也是工作 3-5 年的程序员，常常被"这个数学概念是什么"打断思考节奏，强烈建议你也写一份自己的速查手册——不一定要公开，写给未来的自己即可。

下一步：下一篇会写"算法复杂度速查表”——把 O(1) 到 O(n!) 的所有常见量级，用代码实测验证，并配上对应的真实算法例子。

参考资料

• 《离散数学及其应用》（Kenneth H. Rosen 著）—— 经典教材，集合/图/代数/逻辑四件套全覆盖
• 《算法导论》（Cormen, Leiserson, Rivest, Stein 著）—— 素数、对数、时间复杂度的标准出处
• Python 官方文档 math 模块：https://docs.python.org/3/library/math.html

6 年后补遗：AI 时代的"素数 / 对数 / 离散数学"新意义

本文写于 2019 年 10 月，6 年后回看，3 个老概念都有了"AI 时代"的新应用场景。下面补全 2025-2026 年的视角。

素数新应用：后量子密码学

2019 年 RSA 还在统治加密世界，2024-2025 后量子密码（Post-Quantum Cryptography, PQC）成为新焦点：

• NIST PQC 标准（2024-08 发布）：
  • ML-KEM（原 CRYSTALS-Kyber）—— 密钥封装
  • ML-DSA（原 CRYSTALS-Dilithium）—— 数字签名
  • SLH-DSA（原 SPHINCS+）—— 基于哈希的签名
• 这些算法的核心仍然依赖格密码（Lattice-based） 与素数 / 有限域运算——素数仍是密码学的基石
• 2024-2026 中国国产算法：SM2 椭圆曲线（替代 RSA）、SM3 哈希、SM4 对称——等保 2.0 三级合规要求所有政企系统支持

程序员视角：5 年后做"安全"相关项目，“素数"的概念仍然是入门必备——但要补 PQC 的数学基础（格、向量空间、模运算）。

对数新应用：Transformer 的"对数级别"复杂度

2019 年我们说 O(log n) 是"二分查找的复杂度”。2025 年 O(n²) 才是大模型训练的核心——但对数仍无处不在：

• Token 上下文长度：主流 LLM 上下文从 4K → 32K → 128K → 1M（2024-2025）—— 每翻一倍，显存/算力压力指数级增长
• Attention 机制：标准 Attention 是 O(n²)，2024-2026 各种"线性 Attention”（Performer / Linear Transformer / Mamba）的核心目标就是把 n² 压到 n·log(n) 或 n
• FlashAttention（2022-2024）：把 GPU 显存从 O(n²) 压到 O(log n)，让 128K 上下文成为可能
• KV Cache 压缩：基于对数的位运算，把推理时显存压到原来的 1/4

程序员视角：理解"为什么 Transformer 这么烧钱"，对数 / 复杂度分析就是起点——这块是 2025 后端 + AI 工程师面试必问。

离散数学新应用：大模型 + 知识图谱 + 形式化验证

2019 年我说"离散数学 = 有限世界的工具箱"，2025 年这个工具箱直接喂给大模型：

• RAG（检索增强生成）：本质是集合论 + 关系代数——文档 → 嵌入 → 集合查询 → Top-K
• 知识图谱：用图论建模实体关系，大模型 + 知识图谱成为 2024-2026 企业 AI 的标准架构
• 图神经网络（GNN）：图论 + 深度学习的结合，药物发现、推荐系统、社交网络都有应用
• 形式化验证（Formal Verification）：数理逻辑 + 自动定理证明，Lean 4 + Copilot 2024-2025 在数学证明 + 代码验证上爆发
• Z3 SMT Solver：约束求解器（数理逻辑应用），程序分析、编译器优化、形式化验证的核心

程序员视角：2024-2026 写"AI 应用"，“集合 / 图 / 逻辑” 是底层语言——RAG 是集合操作、知识图谱是图、Chain-of-Thought 是逻辑推理。

3 个老概念的"新意义"对照

5 年前 vs 5 年后：面试题的变化

2019 年面试常问：

• “素数判定有几种优化？”
• “为什么二分查找是 O(log n)？”
• “集合论与 SQL 的对应关系？”

2025-2026 年面试常问：

• “后量子密码和 RSA 的数学基础有什么不同？”
• “Transformer 的 Attention 为什么是 O(n²)？FlashAttention 怎么压到 O(n log n)？”
• “RAG 系统怎么用集合论优化 Top-K 召回？”
• “知识图谱 Embedding 和 GNN 有什么关系？”

5 年变化的核心：3 个老概念都还在用，但应用场景从"系统内部"走向"AI 系统"——素数在加密，对数在 LLM，离散数学在 RAG + 知识图谱。

给"想补数学基础的工程师"的 2025 升级版书单

2019 年我推荐的是 Rosen《离散数学》+ CLRS《算法导论》。2025 年如果重写这个书单，我会加这 3 本：

外加 2 个在线免费资源：

• 3Blue1Brown 的"线性代数的本质"（YouTube / B 站）—— 视觉化理解向量空间
• MIT 6.042J “Mathematics for Computer Science”（OCW）—— 离散数学经典

写在最后：6 年后我还想说

2019 年我说"工作 5 年后被数学卡住，是时候写速查手册"。6 年后我反而更想说：速查手册不够用，要做"数学肌肉"。

• 速查——解决"忘了定义"的问题
• 肌肉——解决"看到新问题能立刻想到数学工具"的问题

2025 年的工程师，“被数学卡住 5 分钟” 和 “看到 AI 问题立刻想到线性代数”，差距是巨大的。

6 年前的我：写完这篇继续 review 代码，偶尔翻一下。
现在的我：写完这篇立刻打开 3Blue1Brown 复习特征值——因为上周 review 的 RAG 系统还在纠结 embedding 维度。

数学不会变老，只是换了个地方等我们回来。

参考资料（2024+ 补充）

• NIST 后量子密码标准（FIPS 203/204/205）
• FlashAttention 论文（2022-2024）
• Mamba: Linear-Time Sequence Modeling
• Microsoft GraphRAG
• Lean 4 形式化证明
• 3Blue1Brown 线性代数本质
• MIT 6.042J Mathematics for CS
• 《Mathematics for Machine Learning》