java - Eratosthenes 问题 Java 筛法

Question

我的作业有问题，需要使用数组。我需要创建埃拉托色尼筛法并打印出所有素数。我很困惑，因为据我所知，我的操作顺序是正确的。这是代码:

        //Declare the array
        boolean numbers [] = new boolean[1000];
        int y = 0;

        //Declare all numbers as true to begin
        for(int i = 2; i < 1000;i++){
            numbers[i] = true;
        }
        //Run loop that increases i and multiplies it by increasing multiples
        for (int x = 2; x < 1000; x++) {

            //A loop for the increasing multiples; keep those numbers below 1000
            //Set any multiple of "x" to false
            for(int n = 2; y < 1000; n++){
            y = n * x;
            numbers[y] = false;
            }
        }

我首先将数组中的所有数字设置为 true。然后第二个循环将从 2 开始“x”，然后在它内部是一个嵌套循环，它将“x”乘以“n”的值，并且“n”将继续增加，只要该乘积(“y ") 低于 1000。一旦 "y"达到该最大值，"x"将增加一个数，并且重复该过程，直到所有非质数都设置为 false。

这是我编写代码时的逻辑，但是当我尝试运行它时，我得到了“ArrayIndexOutOfBoundsException”错误。据我所知，我将所有内容都设置为低于 1000，因此它不应超过数组大小。

我知道它可能不是最有效的算法，因为随着“x”的增加，它会超过它已经超过的数字，但它是我能想到的最简单的算法。

Answer 1

这里:

        for(int n = 2; y < 1000; n++){
        y = n * x;
        numbers[y] = false;
        }

你首先检查y < 1000 ，然后然后初始化并使用它。这是错误的方法。

此外，您可以仅在 x 时运行上述循环是质数。这不会影响正确性，但应该会使您的代码更快。