我正在尝试实现埃拉托斯特尼筛法,但它只适用于小于33的数字。

huangapple go评论76阅读模式
英文:

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

问题

我正在尝试编写一个埃拉托斯特尼筛法的程序,它可以工作,但是如果输入的数字是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);
    }
}
英文:

I'm trying to write a program for the Sieve of Eratosthenes and it works but if the input number is 33 or greater I get this error:

Exception in thread &quot;main&quot; 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)

this is the code that I used

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&lt;Integer&gt; listA = new ArrayList&lt;Integer&gt;();
        ArrayList&lt;Integer&gt; listB = new ArrayList&lt;Integer&gt;();

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

    }
}

答案1

得分: 1

当你收到java.lang.IndexOutOfBoundsException时,意味着在那个时候你已经从listA中移除了所有的数字,因此你不能执行listA.get(0)

我会声明一个布尔数组,并将它们全部设置为true。你可以假装这些是从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);
}
英文:

When you get the java.lang.IndexOutOfBoundsException it means that at that point you have already removed all the numbers from listA, so you can't do listA.get(0)

I would declare an array of booleans and set them all to true. You can pretend these are numbers from 0-n.

Then set every non-prime number to false by starting with 2 and setting multiples to false, etc. Before multiplying you can check if that number is already set to false, that means multiplying this number is not necessary, since all multiples are already set to false. This makes the algorithm significantly faster.

Finally print out all the prime numbers starting from 2.

You could remove Arrays.fill to make it more efficient, but then you need to invert all the other logic, since boolean will default to false.

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

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

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

huangapple
  • 本文由 发表于 2020年3月16日 04:59:53
  • 转载请务必保留本文链接:https://go.coder-hub.com/60697597.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定