新系列：如何在 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 setfor (int i = 2; i < n; i++) {&nbsp; &nbsp; primes.add(i);}//for numbers up to root nfor (int f = 2; f <= Math.sqrt(n); f++){&nbsp; &nbsp; Iterator<Integer> iter = primes.iterator();另外，我建议更改以下内容：primes.remove(current);到：iter.remove();为了避免任何ConcurrentModificationExceptions。最后，您似乎仍然有一个3不在结果中的问题Set，您必须对其进行调试。