什么是埃拉托斯特尼筛法？

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种用于找出一定范围内所有素数的算法。它的基本思想是从2开始，将所有的倍数标记为合数，然后继续找到下一个未被标记的数，重复上述步骤，直到找到所有的素数为止。

具体步骤如下：
1. 创建一个长度为n+1的布尔数组，初始值都为true，表示所有的数都是素数。
2. 从2开始，将2的倍数（除了2本身）标记为false，表示它们不是素数。
3. 找到下一个未被标记为false的数，即3，将3的倍数（除了3本身）标记为false。
4. 重复上述步骤，直到找到所有小于等于n的素数。

最终，数组中为true的索引对应的数就是素数。

埃拉托斯特尼筛法的时间复杂度为O(nlog(logn))，其中n为给定范围内的最大数。

相关问题

埃拉托斯特尼筛法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]。

埃拉托斯特尼筛法python

埃拉托斯特尼筛法是一种用于求解质数的算法，其基本思想是从小到大枚举每一个质数，将其所有的倍数都标记为合数。具体的 Python 实现如下：

def eratosthenes(n):
    prime = [True] * (n+1)
    prime[0] = prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if prime[i]:
            for j in range(i*i, n+1, i):
                prime[j] = False
    return [x for x in range(n+1) if prime[x]]

其中，prime 数组用于记录每个数是否为质数。初始时，所有数都被认为是质数。然后从 2 开始枚举每个质数，将其所有的倍数标记为合数（即将 prime 数组中相应位置设为 False）。最后将 prime 数组中值为 True 的下标返回即可。这些下标即为小于等于 n 的所有质数。