java - 为什么我的算法没有给出预期的输出？

Question

我正在尝试创建 Sieve of Eratosthenes 的 Java 实现算法。

我有以下代码，它运行时给出了不正确的输出。

import java.util.ArrayList;
public class sieveOfEratosthenes {
    private static final ArrayList<Integer> test = new ArrayList<>();
    public static void main (String [] args) {
        java.util.Scanner tempInput = new java.util.Scanner(System.in);
        System.out.println("What number would you like the prime numbers to be generated to?");
        int maxPrime = tempInput.nextInt();
        for(int i = 2; i <= maxPrime; i++) {
            test.add(i);
        }
        getPrimeList(maxPrime);
    }

    private static void getPrimeList(int maxNumber) {
        int sqrtOfNum = (int) Math.sqrt(maxNumber);
        int temp = 0, i = 0;
        int currentPrime = test.get(i);
        boolean completed = false;
        i++;
        //do {
        while((completed == false) && (i < test.size())) {
            if(i >= test.size()) {
                completed = true;
            } else if((temp <= sqrtOfNum) ) {
                removeMultiples(currentPrime);
            }
            i++;
            if (i < test.size()) {
                currentPrime = test.get(i);
            }
        }
        //}while(completed == false && (i < test.size()));
        System.out.println("Prime numbers upto: " + maxNumber + ": " + test);
    }

    private static void removeMultiples(int primeToTest) {
        ArrayList<Integer> temp = new ArrayList<>();
        for (Integer toTest : test) {
            if (!(((toTest) % primeToTest) == 0)) {
                temp.add(toTest);
            }
        }
        test.clear();
        test.addAll(temp);
    }
}

程序给出的输出示例如下:

What number would you like the prime numbers to be generated to?
10
Prime numbers upto: 10: [3, 5, 9]

显然上面例子的输出应该是:

Prime numbers upto: 10: [2, 3, 5, 7]

Answer 1

您将test初始化为[2,3,4,5...]，将currentPrime设置为2( test[0])，删除它的倍数(删除 2)。我相信当 i 变为 2 且 test[2] = 7 时会发生类似的事情。

3 和 5 不会发生这种情况，因为您正在使用 i 来推进 test，但也从 test 中删除项目，所以i 引用的值发生了变化(因为该位置的值发生了变化)。所以在第一次通过 while 循环结束时，i 已经提前到 2 而没有消除 3 或 5 的倍数(如果你使用更大的 maxNumber)。