埃拉托色尼筛法求素数java

埃拉托色尼筛法是一种古老的用于找出一定范围内所有质数的经典算法。在Java中，可以按照以下步骤实现：

1. 定义一个boolean类型的数组`isPrime[]`，大小等于给定的最大整数n+1，初始化所有元素为true，表示它们都是潜在的质数。

2. 从2开始，因为2是最小的质数，将数组中所有的2的倍数都标记为非质数（即`isPrime[2*2..] = false`）。

3. 遍历从3到sqrt(n)，对于每个当前的质数p，如果它的平方小于等于n，并且`isPrime[p]`为true，则遍历p的倍数（`p*p..n`），将这些位置的值设为false，因为它们肯定不是质数。

4. 过程结束后，数组`isPrime[i]`为true的i就是质数。

以下是简单的Java代码实现：

public class SieveOfEratosthenes {
    public static List<Integer> sieveOfEratosthenes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false; // 0和1不是质数

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

        List<Integer> primes = new ArrayList<>();
        for (int p = 2; p <= n; p++)
            if (isPrime[p])
                primes.add(p);

        return primes;
    }

    // 示例
    public static void main(String[] args) {
        int n = 50;
        System.out.println("小于" + n + "的质数：");
        List<Integer> primeList = sieveOfEratosthenes(n);
        for (int prime : primeList)
            System.out.print(prime + " ");
    }
}