质数（Prime Number）是数学中一个基本概念。以下是对质数的详细解析，包括定义、性质、判断方法和应用。
1. 什么是质数？
定义
质数是一个 大于 1 的整数，只能被 1 和它本身整除。
非质数
1 不是质数：它只有一个因子，不符合质数定义。合数：有超过两个因子的正整数。例如，4, 6, 8 是合数。
2. 质数的性质
基本性质
最小的质数是 2：
2
2
2 是唯一的偶质数，所有其他质数都是奇数。 除了 2 和 3，其他质数可表示为
6
k
+
1
6k+1
6k+1 或
6
k
−
1
6k-1
6k−1 的形式：
质数大于 3 时，可以证明它必然位于 6 的倍数的相邻位置上。 质数的分布：
质数在自然数中分布不均匀，随着数值增大，质数出现的频率逐渐减小（受“素数定理”控制）。
唯一性
唯一分解定理：
任意一个大于 1 的正整数，可以唯一分解为若干个质数的乘积。例如：
28
=
2
2
×
7
28 = 2^2 \times 7
28=22×7
45
=
3
2
×
5
45 = 3^2 \times 5
45=32×5
3. 如何判断一个数是否是质数？
基本思路
质数只有两个因子：1 和自身。如果一个数能被小于它的其他数整除，它不是质数。
优化判断
从 2 开始检查：
如果一个数
n
n
n 能被
2
,
3
,
…
,
n
2, 3, \dots, \sqrt{n}
2,3,…,n
整除，那么
n
n
n 不是质数。 不用检查所有数：
n
n
n 的因子成对出现，较大的因子必然是小于等于
n
\sqrt{n}
n
的数的倍数。
常见算法
方法 1：基本算法
逐个检查是否能被 2, 3, …,
n
−
1
n-1
n−1 整除。
public boolean isPrime(int n) {
if (n <= 1) return false; // 1 和小于 1 的数不是质数
for (int i = 2; i < n; i++) {
if (n % i == 0) return false; // 找到因子
}
return true; // 是质数
}
时间复杂度：
O
(
n
)
O(n)
O(n)
方法 2：优化为根号法
只检查到
n
\sqrt{n}
n
，减少计算量。
public boolean isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i * i <= n; i++) { // 只检查到 sqrt(n)
if (n % i == 0) return false;
}
return true;
}
时间复杂度：
O
(
n
)
O(\sqrt{n})
O(n
)
方法 3：6 的倍数法
质数大于 3 时，必然在
6
k
+
1
6k+1
6k+1 或
6
k
−
1
6k-1
6k−1 的位置：
public boolean isPrime(int n) {
if (n <= 1) return false;
if (n <= 3) return true; // 2 和 3 是质数
if (n % 2 == 0 || n % 3 == 0) return false; // 排除 2 和 3 的倍数
for (int i = 5; i * i <= n; i += 6) { // 只检查 6k ± 1
if (n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
}
时间复杂度：
O
(
n
)
O(\sqrt{n})
O(n
)
批量判断质数：埃拉托色尼筛法
如果需要在一定范围内判断所有质数，可以用筛法，效率更高。
算法思想
从
2
2
2 开始，将其所有倍数标记为非质数。找到下一个未被标记的数（它是质数），并标记它的所有倍数。重复步骤直到
n
\sqrt{n}
n
。未被标记的数都是质数。
代码实现
public List
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
isPrime[0] = false;
isPrime[1] = false; // 0 和 1 不是质数
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false; // 标记 i 的倍数
}
}
}
List
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
primes.add(i); // 未被标记的数是质数
}
}
return primes;
}
4. 示例与输出
质数判断示例
输入：17, 18, 19 输出：
17
17
17 是质数。
18
18
18 不是质数（可被 2 和 3 整除）。
19
19
19 是质数。
埃拉托色尼筛法输出
输入：
n
=
30
n = 30
n=30 输出：
2
,
3
,
5
,
7
,
11
,
13
,
17
,
19
,
23
,
29
2, 3, 5, 7, 11, 13, 17, 19, 23, 29
2,3,5,7,11,13,17,19,23,29
5. 应用场景
加密算法：
公钥加密（如 RSA）依赖于质数的分解难度。 数论研究：
最大公约数、最小公倍数等计算常涉及质数。 随机数生成：
质数在伪随机数生成算法中被广泛使用。 算法优化：
素数相关优化可以提升算法效率。
6. 总结
质数定义：大于 1 且只有 1 和自身两个因子的整数。判断方法：
简单整除法（从 2 开始逐个检查）。根号法（检查到
n
\sqrt{n}
n
）。6 的倍数优化。 批量计算：使用埃拉托色尼筛法快速找出范围内所有质数。应用广泛：质数是数论和计算机科学的重要基础。
通过优化和算法的选择，可以高效解决质数相关问题。