新系列：如何在 java 中实现 Eratosthenes 的筛子

Question

我是新手，我在一本书中发现了这个问题：实施埃拉托色尼筛法：一种计算素数的方法，为古希腊人所知。选择一个 n。此方法将计算直到 n 的所有素数。首先将从 2 到 n 的所有数字插入到一个集合中。然后擦除所有2的倍数（2除外）；即 4、6、8、10、12、……。擦除所有 3 的倍数；也就是说，6、9、12、15、……。提高到 。然后打印集合。我写了这段代码：import java.util.Iterator;import java.util.Set;import java.util.TreeSet;public class SieveOfEratosthenes {    public static void main (String[] args){        System.out.print(generatePrime(20));    }    public static Set generatePrime(int n){        Set<Integer> primes = new TreeSet<>();        Iterator<Integer> iter = primes.iterator();        //generate all numbers up to n and add them to the set        for (int i = 2; i < n; i++){            primes.add(i);        }        //for numbers up to root n        for (int f = 2; f <= Math.sqrt(n); f++){            while (iter.hasNext()){                int current = iter.next();                if (current % f == 0 && current != 2){                    primes.remove(current);                }            }        }        return primes;    }}问题是while循环中的代码没有实现。当我调试程序时，我发现 hasNext() 返回 null。尽管列表包含数字，但我无法弄清楚这样做的原因。这是我从代码中得到的输出：[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]Process finished with exit code 0先感谢您！

Answer 1

要创建的Iterator 前添加元素的Set时候，你应该创建它后（里面的for循环）：

Set<Integer> primes = new TreeSet<>();

//generate all numbers up to n and add them to the set

for (int i = 2; i < n; i++) {

    primes.add(i);

}

//for numbers up to root n

for (int f = 2; f <= Math.sqrt(n); f++){

    Iterator<Integer> iter = primes.iterator();

另外，我建议更改以下内容：

primes.remove(current);

到：

iter.remove();

为了避免任何ConcurrentModificationExceptions。

最后，您似乎仍然有一个3不在结果中的问题Set，您必须对其进行调试。