java如何寻找质数

判断质数的基本方法

质数是指大于1的自然数，除了1和它本身外没有其他约数。Java中判断一个数是否为质数可以通过以下方法实现：

public static boolean isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

该方法从2开始检查到√n，如果能被其中任意一个数整除，则不是质数。

埃拉托斯特尼筛法

当需要找出一定范围内的所有质数时，埃拉托斯特尼筛法是更高效的算法：

public static void sieveOfEratosthenes(int n) {
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);

    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            System.out.print(i + " ");
        }
    }
}

该算法通过标记非质数的倍数来筛选质数，时间复杂度为O(n log log n)。

优化后的质数判断

对于大数判断，可以进一步优化：

public static boolean isPrimeOptimized(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;
}

这种方法跳过了明显不是质数的数（如偶数），只检查6k±1形式的数。

并行处理大范围质数

对于非常大的范围，可以使用并行流处理：

public static List<Integer> primesInParallel(int limit) {
    return IntStream.rangeClosed(2, limit)
            .parallel()
            .filter(n -> isPrime(n))
            .boxed()
            .collect(Collectors.toList());
}

这种方法利用多核处理器并行计算，适合处理大数据集。