开发者社区> 问答> 正文

我正在尝试实现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);

    }
}

问题来源:Stack Overflow

展开
收起
montos 2020-03-23 16:36:16 549 0
1 条回答
写回答
取消 提交回答
  • 当您获得时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);
            }
    

    回答来源:Stack Overflow

    2020-03-23 16:36:52
    赞同 展开评论 打赏
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载