Java中求素数的高效算法与应用示例

1. 试除法

试除法是最基本的判断素数的方法，其思路是：对于一个整数n，如果它不能被2到n-1之间的任何整数整除，那么n就是素数。

代码示例：

java

public class PrimeNumber {

public static boolean isPrime(int n) {

if (n <= 1) {

return false;

for (int i = 2; i < n; i++) {

if (n % i == 0) {

return false;

return true;

public static void main(String[] args) {

int num = 17;

if (isPrime(num)) {

System.out.println(num + " 是素数");

} else {

System.out.println(num + " 不是素数");

效率分析：

时间复杂度：O(n)，因为需要从2到n-1逐一检查是否能整除。

空间复杂度：O(1)，只需要常数级别的额外空间。

2. 优化试除法

可以通过减少检查的范围来提高试除法的效率。例如，只需要检查2到n的平方根之间的整数即可。

代码示例：

java

public class PrimeNumber {

public static boolean isPrime(int n) {

if (n <= 1) {

return false;

int sqrtN = (int) Math.sqrt(n);

for (int i = 2; i <= sqrtN; i++) {

if (n % i == 0) {

return false;

return true;

public static void main(String[] args) {

int num = 17;

if (isPrime(num)) {

System.out.println(num + " 是素数");

} else {

System.out.println(num + " 不是素数");

效率分析：

时间复杂度：O(sqrt(n))，因为只需要检查到n的平方根。

空间复杂度：O(1)，同样只需要常数级别的额外空间。

3. 埃拉托斯特尼筛法

埃拉托斯特尼筛法是一种更高效的求素数的方法，其基本思想是：从2开始，将每个素数的倍数标记为合数，直到达到指定的上限。

代码示例：

java

import java.util.ArrayList;

import java.util.List;

public class PrimeNumber {

public static List sieveOfEratosthenes(int n) {

boolean[] isComposite = new boolean[n + 1];

List primes = new ArrayList<>;

for (int i = 2; i <= n; i++) {

if (!isComposite[i]) {

primes.add(i);

for (int j = i i; j <= n; j += i) {

isComposite[j] = true;

return primes;

public static void main(String[] args) {

int num = 50;

List primes = sieveOfEratosthenes(num);

System.out.println("小于或等于 " + num + " 的素数有：");

for (int prime : primes) {

System.out.print(prime + " ");

效率分析：

时间复杂度：O(n log log n)，因为每个合数只被标记一次。

空间复杂度：O(n)，需要一个布尔数组来标记合数。

4. 应用示例：加密算法中的素数应用

素数在加密算法中有着广泛的应用，例如RSA加密算法。RSA算法依赖于两个大素数的乘积来生成密钥对。

代码示例（简化版RSA密钥生成）：

java

import java.math.BigInteger;

import java.util.Random;

public class RSAKeyGenerator {

public static BigInteger[] generateKeyPair(int bitLength) {

BigInteger p, q, n, phi, e, d;

Random rnd = new Random;

p = BigInteger.probablePrime(bitLength / 2, rnd);

q = BigInteger.probablePrime(bitLength / 2, rnd);

n = p.multiply(q);

phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));

e = BigInteger.valueOf(65537);

d = e.modInverse(phi);

return new BigInteger[]{e, d, n};

public static void main(String[] args) {

int bitLength = 2048;

BigInteger[] keys = generateKeyPair(bitLength);

System.out.println("公钥 (e, n): " + keys + ", " + keys);

System.out.println("私钥 (d, n): " + keys + ", " + keys);

效率分析：

时间复杂度：生成密钥对的时间复杂度取决于素数生成的时间复杂度，通常是O(bitLength^3)。

空间复杂度：O(bitLength)，因为需要存储密钥对的数值。

以上算法和应用示例展示了在Java中求素数的高效方法及其在实际应用中的重要性。根据具体需求，可以选择合适的算法来实现最佳性能。