java - 新套装 : How to implement the sieve of Eratosthenes in java

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

您在将元素添加到Set之前之前创建了Iterator，而实际上应该在之后(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();

避免任何ConcurrentModificationException。

<小时/>

最后，您似乎仍然遇到一个问题，即 3 不在生成的 Set 中，您必须对其进行调试。