埃拉托斯特尼筛法java

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种用于找出一定范围内所有素数的算法。它的基本思想是从2开始，将每个素数的倍数标记为非素数，直到遍历完所有小于给定范围的数。以下是使用Java实现埃拉托斯特尼筛法的示例代码：

import java.util.ArrayList;
import java.util.List;

public class SieveOfEratosthenes {
    public static List<Integer> findPrimes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }

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

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

        return primes;
    }

    public static void main(String[] args) {
        int n = 30;
        List<Integer> primes = findPrimes(n);
        System.out.println("Primes less than or equal to " + n + ": " + primes);
    }
}

上述代码中，`findPrimes`方法接受一个整数n作为参数，返回小于等于n的所有素数的列表。首先，创建一个布尔数组`isPrime`，用于标记每个数是否为素数。然后，从2开始遍历到n，将每个数都标记为素数。接下来，从2开始遍历到√n，如果当前数是素数，则将其倍数标记为非素数。最后，遍历数组，将标记为素数的数添加到结果列表中。

运行上述代码，将输出小于等于30的所有素数：[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]。