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