java用筛选法判断素数

在Java中，我们可以使用筛选法（Sieve of Eratosthenes）来判断一个数是否为素数。这是一种古老的算法，通过逐步排除能整除该数的非素数因子，最终确定该数是否为素数。以下是简单的步骤：

1. 创建一个布尔数组，大小从2到你要检查的最大值（例如n），并将所有元素初始化为true。数组的索引代表每个自然数，值表示该数是否可能是素数。

2. 从第一个质数2开始，遍历数组，将所有2的倍数标记为false，因为除了2以外的偶数都不是素数。

3. 继续寻找下一个未标记为false的数字（即下一个质数），这里是3。然后将3的所有倍数（不是已经标记过的）标记为false。

4. 重复此过程，每次增加一个当前找到的质数，直到大于√n。这是因为如果n有一个因子大于它的平方根，那么n必然有一个小于它平方根的因子，我们在之前的操作中已经处理过了。

5. 最后，如果没有在数组中找到某个数的索引为false，则这个数就是素数。

public boolean isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    boolean[] primes = new boolean[n + 1];
    Arrays.fill(primes, true);
    primes[0] = primes[1] = false;

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

    return primes[n];
}