Java求质数的几种常用算法分析

针对“Java求质数的几种常用算法分析”，我们可以从以下几个方面进行讲解：

算法分析

• 方法1：暴力枚举
• 方法2：素数筛法

方法1：暴力枚举

这种算法比较简单，直接从1到n枚举每一个数字，然后依次验证数字是否为质数。具体实现如下：

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;
}

由于暴力枚举法需要从1到n枚举每一个数字，因此时间复杂度为O(N)，效率较低。

方法2：素数筛法

相比于暴力枚举，素数筛法是一种更为高效的算法。基本思路是：首先初始化一个长度为n+1的布尔型数组，然后将数组中所有值赋为true，将0和1的位置赋为false，再从2开始遍历数组，将当前数字的倍数全部标记为false，直到遍历到n的位置为止，最后剩下的true即为质数。具体实现如下：

public static int[] sieve(int n) {
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = false;
    isPrime[1] = false;
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    int[] primeNumbers = new int[n + 1];
    int count = 0;
    for (int i = 0; i <= n; i++) {
        if (isPrime[i]) {
            primeNumbers[count++] = i;
        }
    }
    return Arrays.copyOf(primeNumbers, count);
}

由于素数筛法只需要遍历一次数组，因此时间复杂度为O(N*log(log(N)))，效率比暴力枚举法高得多。

案例示例

假设我们需要求出200以内的所有质数，我们可以使用上面的两种算法进行测试。具体代码如下：

暴力枚举法示例

public static void main(String[] args) {
    for (int i = 2; i <= 200; i++) {
        if (isPrime(i)) {
            System.out.print(i + " ");
        }
    }
}

输出结果：

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 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 

素数筛法示例

public static void main(String[] args) {
    int[] primeNumbers = sieve(200);
    for (int i = 0; i < primeNumbers.length; i++) {
        if (primeNumbers[i] == 0) {
            break;
        }
        System.out.print(primeNumbers[i] + " ");
    }
}

输出结果：

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 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 

从输出结果可以看出，两种算法均正确实现了求解200以内所有质数的功能。

结论

综上所述，在Java中求解质数的问题，暴力枚举法和素数筛法是比较常用的两种方法。其中暴力枚举法虽然简单易懂，但效率较低；而素数筛法则更为高效，但代码实现可能稍微有些复杂。需要根据具体实际需求场景选择合适的算法来解决问题。