素数(又称质数)是指大于1的自然数中,除了1和它本身以外不再有其他因数的数。即:若一个正整数n满足:当且仅当它的正因数仅有1和n本身时,n为素数。
例如:
• 2是素数(因数:1, 2)
• 3是素数(因数:1, 3)
• 4不是素数(因数:1, 2, 4)
• 1不是素数(定义排除)
• 0不是素数(非正整数)
这是由唯一分解定理(算术基本定理)决定的:任一大于1的整数,若不计顺序,其质因数分解形式唯一。若允许1为素数,则如12可表示为:
12 = 2×2×3 = 1×2×2×3 = 1²×2×2×3 = …(无限种形式)
导致分解不唯一,破坏数学体系的严谨性。因此现代数学严格规定:1既不是素数,也不是合数。
对整数n,遍历2至n−1,若存在能整除n的数,则n非素数;否则为素数。
public static boolean isPrimeBasic(int n) {
if (n <= 1) return false;
for (int i = 2; i < n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
时间复杂度为O(n),当n较大时(如10⁷),循环次数激增,效率极低。仅适用于教学演示或极小数值场景。
| 输入n | 预期结果 | 说明 |
|---|---|---|
| 2 | true | 最小素数 |
| 17 | true | 奇素数 |
| 25 | false | 5²,合数 |
| 1 | false | 非素数 |
| 0 | false | 非正整数 |
| -7 | false | 负数非素数 |
若n为合数,则必存在一个因数≤√n。因为若n = a×b,且a ≤ b,则a ≤ √n(否则a×b > √n×√n = n,矛盾)。
因此只需检查2至⌊√n⌋区间即可,将复杂度降至O(√n)。
public static boolean isPrimeOptimized(int n) {
if (n <= 1) return false;
if (n == 2) return true;
if (n % 2 == 0) return false; // 排除偶数
for (int i = 3; i * i <= n; i += 2) {
if (n % i == 0) return false;
}
return true;
}
| 方法 | 循环次数 | 预估耗时(纳秒) |
|---|---|---|
| 朴素版 | 999981 | ≈12,000 |
| 开方优化版 | 500 | ≈60 |
所有大于3的素数必形如6k±1。因此可先排除2、3的倍数,再以步长6遍历5、7、11、13…
public static boolean isPrime6k(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
}
对n = 10⁷,循环次数从√n≈3162降至≈1054,提速约3倍;对n = 10⁹,循环次数从31622降至16666。
当n接近Long.MAX_VALUE(9,223,372,036,854,775,807)时,i * i可能溢出为负数,导致循环条件失效。
public static boolean isPrimeLong(long n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (long i = 5; i <= Math.sqrt(n); i += 6) {
if (n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
}
使用Math.sqrt(n)时需注意:浮点精度误差可能导致√n略小于真实值,但因i为整数,且循环条件为i <= sqrt(n),实际仍覆盖所有可能因数,结果正确。
更严谨方案:用n / i < i替代i * i > n,防止乘法溢出。
public static boolean isPrimeSafe(long n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (long i = 5; n / i >= i; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
}
对超大整数(如密码学中的2048位素数),可使用java.math.BigInteger:
import java.math.BigInteger;
public static boolean isPrimeBigInteger(BigInteger n) {
if (n.compareTo(BigInteger.ONE) <= 0) return false;
return n.isProbablePrime(100); // 100轮Miller-Rabin测试
}
isProbablePrime(certainty)中,certainty越高,误判为素数的概率越低(≈ 2-certainty)。certainty=100时,错误概率低于10-30,可视为确定性结果。
素数定义域为正整数,因此:
2是唯一偶素数。若跳过偶数优化,需单独处理:先判断n==2返回true,再判断n%2==0返回false,避免遗漏。
见定义章节。若在算法中误判1为素数,会导致:
Long.MAX_VALUE = 2⁶³−1 = 9223372036854775807,是素数!但计算时:
| 数值范围 | 朴素版 | 开方版 | 6k优化版 | BigInteger |
|---|---|---|---|---|
| 1~10³ | 0.02 | 0.01 | 0.01 | 1.2 |
| 1~10⁵ | 2.1 | 0.3 | 0.1 | 12.5 |
| 1~10⁷ | 210.0 | 30.0 | 10.5 | 1200.0 |
public static List getPrimesInRange(int start, int end) {
List primes = new ArrayList<>();
for (int n = start; n <= end; n++) {
if (isPrime6k(n)) primes.add(n);
}
return primes;
}
输出结果:[101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
回文素数:既是素数又是回文数(如11、101、131)。
public static boolean isPalindromicPrime(int n) {
return isPrime6k(n) && new StringBuilder(n+"").reverse().toString().equals(n+"");
}
基于素数判定,实现分解:
public static List primeFactorization(int n) {
List factors = new ArrayList<>();
for (int i = 2; i * i <= n; i++) {
while (n % i == 0) {
factors.add(i);
n /= i;
}
}
if (n > 1) factors.add(n); // 剩余素数
return factors;
}
例:60 → [2, 2, 3, 5]
用减法模拟除法,适用于受限环境(如嵌入式):
public static boolean isDivisible(int n, int d) {
while (n >= d) n -= d;
return n == 0;
}
但效率极低,仅作拓展思维。