质数是大于 1 的整数，并且恰好有两个因数：1 和它本身。素数是所有整数的组成部分——每个整数都可以表示为素数的乘积。
前 25 个素数
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
请注意，2 是唯一的偶素数。所有其他偶数都可以被 2 整除。
方法一：试除法
测试一个数是否为素数的最简单方法是检查是否有任意数能整除它的平方根。
关键见解： 如果 n 有一个大于 √n 的因子，则它也有一个小于 √n 的相应因子。所以你只需要检查√n即可。
算法：
- 如果 n < 2，则不是素数
- 如果 n = 2，则质数
- 如果n是偶数（2除外），不是素数
- 检查从 3 到 √n 的所有奇数
- 如果有n被整除，则不是素数
- 否则，灌注
示例：97 是质数吗？
√97 ≈ 9.85，因此检查 9 以内的素数：2, 3, 5, 7
- 97 ÷ 2 = 48.5（非整数）
- 97 ÷ 3 = 32.33...（不是整数）
- 97 ÷ 5 = 19.4（非整数）
- 97 ÷ 7 = 13.86（不是整数）
未找到约数 — 97 是质数。
示例：91 是素数吗？
√91 ≈ 9.54，最多检查 9：2,3,5,7
- 91 ÷ 7 = 13（整数！）
91 不是质数 — 91 = 7 × 13。
方法 2：埃拉托斯特尼筛法
埃拉托斯特尼筛法可以找到所有达到给定极限的素数。它快速而优雅，由希腊数学家埃拉托色尼 (Eratosthenes) 于公元前 240 年左右发明。
查找 50 以内的所有素数：
1.写出数字2到50 2. 从 2（第一个素数）开始。划掉所有 2 的倍数（4、6、8...） 3. 移至下一个未划掉的数字： 3. 划掉 3 的倍数（9、15、21...） 4. 下一个未划线的： 5. 划掉 5 的倍数 (25, 35...) 5. 下一个未划线的： 7. 划掉 7 的倍数（49...） 6. 当达到√50 ≈ 7.07 时停止 7. 剩下的所有未交叉的数字都是质数
** 50 以内的质数：** 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
100 以内的素数：完整列表
| 范围 | 素数 |
|---|---|
| 1–10 | 2, 3, 5, 7 |
| 11-20日 | 11, 13, 17, 19 |
| 21–30 | 23, 29 |
| 31–40 | 31, 37 |
| 41–50 | 41, 43, 47 |
| 51–60 | 53, 59 |
| 61–70 | 61, 67 |
| 71–80 | 71, 73, 79 |
| 81–90 | 83, 89 |
| 91–100 | 97 |
100以下的素数有25个。
快速整除测试
在进行完全除法之前，请检查以下规则：
| 可除以 | 如果... |
|---|---|
| 2 | 最后一位数字是偶数 (0,2,4,6,8) |
| 3 | 能被3整除的数字之和 |
| 5 | 最后一位数字是 0 或 5 |
| 7 | 没有简单的规则——只是除法 |
| 11 | 可被 11 整除的交替数字和 |
示例：143 是素数吗？
- 甚至没有 ✓
- 1+4+3 = 8，不能被 3 整除 ✓
- 不以 0 或 5 结尾 ✓
- √143 ≈ 11.96，最多检查 11
- 143 ÷ 7 = 20.43 ✓
- 143 ÷ 11 = 13 — 可整除！
143 = 11 × 13。非素数。
为什么素数很重要
密码学： RSA 加密 - 用于保护网上银行、HTTPS 和电子邮件 - 依赖于这样一个事实：将两个大素数相乘很容易，但将结果分解回素数却极其困难。
计算机科学： 哈希表、随机数生成器和校验和使用素数的属性。
纯数学： 素数的分布仍然是数学中最深奥的未解决问题之一——黎曼猜想。
有趣的主要事实
- 已知最大的素数（截至 2024 年）有超过 4100 万位数字
- 孪生素数是相差 2 的素数（11 和 13、17 和 19、41 和 43）
- 素数有无穷多个——由欧几里得在公元前 300 年左右证明
- 哥德巴赫猜想（自 1742 年以来未经证实）：每个大于 2 的偶数都是两个素数之和