质数
zhì shù
质数是大于1的整数，只能被1和它本身整除。
Definition
质数是大于 $1$ 且只能被 $1$ 和它本身整除的正整数，恰好只有两个正因数。数 $1$ 既不是质数也不是合数，根据算术基本定理，每个大于 $1$ 的整数要么是质数，要么可以唯一地分解为若干质数的乘积。形式上，$\mathbb{Z}$ 中的质数 $p$ 是一个不可约元素：若 $p \mid ab$，则 $p \mid a$ 或 $p \mid b$。
Example
$7$ 是质数，因为只有 $1 \times 7 = 7$；但 $6$ 不是质数，因为 $2 \times 3 = 6$ 使它拥有四个因数。$13$ 是质数（因数：$1, 13$），而 $15$ 是合数（因数：$1, 3, 5, 15$）；$30$ 以内的质数有 $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$。梅森质数的形式为 $2^p - 1$（例如 $2^7 - 1 = 127$），RSA 加密依赖于对大质数 $p, q$ 分解 $n = pq$ 的困难性。
Key Insight
可以把质数想象成无法排成一行以上的矩形的数：$7$ 个点只能排成 $1$ 行 $7$ 个。$2$ 是唯一的偶质数，埃拉托斯特尼筛法通过从 $2$ 开始逐个划掉每个质数的倍数，找出 $n$ 以内的所有质数。质数是 $\mathbb{Z}$ 中乘法的"原子"；质数定理指出 $\pi(n) \sim n / \ln(n)$，其中 $\pi(n)$ 表示不超过 $n$ 的质数个数，而黎曼猜想若被证明，将给出该定理误差的已知最紧上界。