时间戳

首页 > 解决方案 > 我正在尝试实施 Eratosthenes 筛，但它仅适用于小于 33 的数字

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

问题描述

我正在尝试为 Eratosthenes 的筛子编写一个程序，它可以工作，但如果输入数字为 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);

    }
}

标签： javasieve-of-eratosthenes

解决方案

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

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

然后通过从 2 开始并将倍数设置为 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);
        }

推荐阅读