我正在尝试实施 eratosthenes 筛法，但它仅适用于小于 33 的数字

Question

我正在尝试为埃拉托色尼筛法编写一个程序，它可以运行，但如果输入数字为 33 或更大，我会收到此错误：

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
    at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64)
    at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70)
    at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:248)
    at java.base/java.util.Objects.checkIndex(Objects.java:373)
    at java.base/java.util.ArrayList.get(ArrayList.java:425)
    at Main.main(Main.java:23)

这是我使用的代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner read = new Scanner(System.in);
        int nr = read.nextInt();

        ArrayList<Integer> listA = new ArrayList<Integer>();
        ArrayList<Integer> listB = new ArrayList<Integer>();

        for (int i = 2; i <= nr; i++)
                listA.add(i);
        //System.out.println(listA);
        int m = 2;
        listB.add(m);
        while (m <= nr-2) {
            listA.removeAll(Arrays.asList(m));
            for (int j = m*2; j <= nr; j = j + m) {
                listA.removeAll(Arrays.asList(j));
            }
            m = listA.get(0);
            listB.add(m);
        }
        System.out.println(listB);

    }
}

Answer 1

当你得到 java.lang.IndexOutOfBoundsException 时，这意味着你已经从 listA 中删除了所有数字，所以你不能做 listA.get(0)

我会声明一个布尔数组并将它们全部设置为真。你可以假装这些是从 0 到 n 的数字。

然后通过从 2 开始并将倍数设置为 false 等将每个非质数设置为 false。在相乘之前，您可以检查该数字是否已设置为 false，这意味着不需要乘以该数字，因为所有倍数都已设置为 false。这使算法明显更快。

最终打印出从2开始的所有素数

您可以删除 Arrays.fill 以提高效率，但随后您需要反转所有其他逻辑，因为布尔值将默认为 false。

        boolean[] primeNumbers = new boolean[nr + 1];
        Arrays.fill(primeNumbers, true);

        int m = 2;
        while (m <= Math.sqrt(nr)) {
            if (primeNumbers[m])
                for (int j = m * 2; j <= nr; j = j + m) {
                    primeNumbers[j] = false;
                }
            m++;
        }

        for (int i = 2; i <= nr; i++) {
            if (primeNumbers[i]) System.out.println(i);
        }

我正在尝试实施 eratosthenes 筛法，但它仅适用于小于 33 的数字

I'm trying to implement sieve of eratosthenes but it works only for numbers smaller then 33

java

sieve-of-eratosthenes