质数定义及基本概念
什么是质数？
在数学领域，质数（Prime Number），又称素数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。换句话说，质数只能被1和它自身整除。例如，2、3、5、7都是质数，因为它们无法被其他整数整除而不留余数。
与之相对的是合数（Composite Number），即除了1和它本身外，还能被其他自然数整除的数。值得注意的是，数字1既不是质数也不是合数，它是自然数的单位，具有独特的数学地位。
质数与合数的区别
| 特征 | 质数 (Prime) | 合数 (Composite) | 数字 1 |
|---|---|---|---|
| 因数个数 | 恰好2个 (1和它本身) | 多于2个 | 仅1个 (1) |
| 最小值 | 2 | 4 | 1 |
| 奇偶性 | 除2外均为奇数 | 有奇有偶 | 奇数 |
质数的核心性质与考点
理解质数的性质是解决数论问题的关键。以下列举了考试中高频出现的质数性质：
① 无穷性
质数的个数是无限的。这一结论由古希腊数学家欧几里得首先证明。无论我们找到多少个质数，总能找到一个更大的质数。这一性质保证了数学世界的丰富性。
② 唯一分解定理（算术基本定理）
任何一个大于1的自然数，要么本身就是质数，要么可以分解为几个质数的乘积，而且这种分解方式是唯一的（不考虑因数的顺序）。例如，12 = 2 × 2 × 3，这是唯一的一种质因数分解形式。
③ 孪生质数
如果两个质数之差为2，则称这两个质数为孪生质数。例如：(3, 5), (5, 7), (11, 13), (17, 19)等。孪生质数猜想认为存在无穷多对孪生质数，这至今仍是未解之谜。
④ 哥德巴赫猜想
每个大于2的偶数都可以表示为两个质数之和。例如：4 = 2 + 2, 10 = 3 + 7, 20 = 3 + 17。这是数论中著名的未解决问题，虽然尚未完全证明，但在计算机验证范围内均成立。
100以内质数表及记忆技巧
熟练掌握100以内的质数是解决基础数学问题的前提。以下是100以内的所有质数，共计25个。
| 1-25 | 26-50 | 51-75 | 76-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 |
1415926535，8979323846（圆周率前10位，无帮助，改用以下）
二三五七和十一，十三十三十九里，二十三三十七九，四十一四十三四七，五三五六十一三，六七七一三，七九八三八九七。
更简单的记忆法：记住个位是1,3,7,9的数（除了5的倍数），并排除合数。例如：11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97。
质数判定与质因数分解方法
试除法（Trial Division）
这是最基础也是最常用的判定方法。适用于判断单个数是否为质数。
- 若该数小于2，则不是质数。
- 若该数等于2，则是质数。
- 若该数大于2且为偶数，则不是质数。
- 若该数大于2且为奇数，则用小于其平方根的所有质数依次去除它。若能整除，则不是质数；若都不能整除，则是质数。
示例：判断97是否为质数。
√97 ≈ 9.8，所以只需检查小于9.8的质数：2, 3, 5, 7。
- 97不能被2整除（奇数）。
- 9+7=16，不能被3整除。
- 个位不是0或5，不能被5整除。
- 97 ÷ 7 = 13...6，不能被7整除。
因此，97是质数。
短除法（Short Division）
用于将一个合数分解为质因数的乘积。
步骤：
- 用最小的质数2去除该数，若有余数，则用下一个质数3去除，依此类推。
- 直到商为1为止。
- 所有的除数即为该数的质因数。
示例：分解120。
120 ÷ 2 = 60
60 ÷ 2 = 30
30 ÷ 2 = 15
15 ÷ 3 = 5
5 ÷ 5 = 1
所以，120 = 2 × 2 × 2 × 3 × 5 = 2³ × 3 × 5。
埃拉托斯特尼筛法（Sieve of Eratosthenes）
这是一种高效找出小于指定整数n的所有质数的算法。
- 列出2到n的所有整数。
- 从2开始，将2的倍数（除2本身外）标记为合数。
- 找到下一个未被标记的数（即下一个质数），将其倍数标记为合数。
- 重复步骤3，直到处理的质数的平方大于n。
- 未被标记的数即为质数。
此方法在计算机编程和数学竞赛中非常常见，适合批量查找质数。
质数研究的历史沿革
欧几里得《几何原本》
欧几里得在《几何原本》中首次系统研究了质数，并证明了质数有无穷多个。这是数学史上最早关于质数的系统性论述。
埃拉托斯特尼发明筛法
埃拉托斯特尼发明了著名的“埃氏筛法”，用于高效寻找质数，这一方法至今仍被使用。
费马大定理与费马素数
皮埃尔·德·费马研究了形如 2^(2^n) + 1 的数，称为费马素数。他还提出了费马小定理，成为现代数论的基础。
黎曼猜想
伯恩哈德·黎曼发表了关于黎曼ζ函数的论文，提出了黎曼猜想。该猜想与质数的分布规律密切相关，是千禧年七大难题之一。
质数在密码学中的应用
随着计算机科学的发展，大质数的分解困难性成为RSA加密算法的基础。质数理论从纯数学走向了实际应用，保护了现代信息安全。