定义
自然数分为三类：一、质数和合数。
- 质数是大于 1、恰好有两个约数的自然数：1 和自身。例如：2、3、5、7、11、13、17、19、23、29……
- 合数是大于 1、有两个以上约数的自然数。例如：4、6、8、9、10、12、14、15、16……
数字 1 既不是质数也不是合数。
质数与合数
质数表
100 以内的质数：2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97。
质数有无限多个。这一点早在古希腊就被欧几里得证明了。
埃拉托斯特尼筛法
埃拉托斯特尼筛法是查找给定数 N 以内所有质数的算法。步骤：
- 写出 2 到 N 的所有数。
- 第一个数（2）是质数。划掉所有 2 的倍数（4、6、8、10……）。
- 下一个未被划掉的数（3）是质数。划掉所有 3 的倍数（6、9、12……）。
- 继续，直到达到其平方大于 N 的数。
- 所有未被划掉的数都是质数。
质因数分解
任何合数都可以分解为质因数——即表示为质数的乘积。
例如：84 = 2 · 2 · 3 · 7 = 2² · 3 · 7；360 = 2³ · 3² · 5。
这样的分解是唯一的（不计因数的顺序）——这就是算术基本定理。
性质
- 质数有无限多个（欧几里得定理）。
- 唯一的偶质数是 2。其他所有质数都是奇数。
- 任何大于 1 的自然数要么是质数，要么唯一地分解为质因数。
- 孪生质数（形如 (p, p + 2) 的对）有无限多——这是一个尚未证明的猜想。
