Eratosthenes 筛法不会筛选素数

Question

对于我正在为我的类之一做的作业，我们必须实施埃拉托色尼筛法。我已经尝试了七次来获得一个有效的代码，并尝试合并我研究过的众多解决方案。我终于有了一个可以输出数字的。不幸的是，它同时打印合数和素数，但不打印 2.

我的代码如下：

public class EratosthenesSieveAttempt6 {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int limit;

        System.out.print("Please enter the highest number to check "
                + "(number must be greater than 2): ");

        limit = keyboard.nextInt();

        while (limit <= 2){
          System.out.println("Error - number must be greater than 2.");
          System.out.println("Please enter the highest number to check: ");
          limit = keyboard.nextInt();
        }

        boolean[] numbers = new boolean[limit + 1];
        int newPrime = 2;

        for(int i = 0; i < limit + 1; i++){
          numbers[i] = true;       
        }

        for(int j = 1; j < limit + 1; j++) {
          if (j % 2 == 0) {
           numbers[j] = false;   
           }

        for(int k = j + 1; k < limit + 1; k++) {
           if(numbers[k] == true){
             j = k;

        System.out.println(k);
               }
            }
         }
       }
    }

我怀疑我的循环有问题。我为我的前两个循环修复了 i 和 j 变量，以便它可以从 2 开始打印出来，问题似乎是在我初始化之后它没有将合数标记为 false数组到 true.

预先感谢您的帮助。

Answer 1

这是我前几天写的埃拉托色尼筛法的实现：

import java.util.BitSet;

public static BitSet composite(int max) {
    BitSet composite = new BitSet(max);
    max = composite.size();
    for (int i = 4; i < max; i += 2) composite.set(i, true);
    for (int i = 9; i < max; i += 6) composite.set(i, true);
    int p = 5;
    while (p*p < max) {
        if (!composite.get(p)) {
            for (int i = p*p; i < max; i += p*2) composite.set(i, true);
        }
        p += 2;
        if (p*p >= max) break;
        if (!composite.get(p)) {
            for (int i = p*p; i < max; i += p*2) composite.set(i, true);
        }
        p += 4;
    }
    return composite;
}

备注：

BitSet分配64位字，所以大小可能比你要求的大（例如，如果你要求它上升到1000，它会上升到1024；这就是[=12=的原因] 靠近顶部）
明确地获取 2、3，然后
依赖于所有大于 3 的素数都等于 1 或 5 mod 6 的事实；这就是最终循环在加 2 和 4

它 returns 一个 BitSet 告诉你哪些数字是合数。仅从中提取素数的一种方法是：

public static int[] primes(BitSet composite) {
    int size = composite.size() - 2 - composite.cardinality();
    int[] primes = new int[size];
    int index = 0;
    for (int i = 2; i < composite.size(); i++) {
        if (!composite.get(i)) primes[index++] = i;
    }
    return primes;
}

Eratosthenes 筛法不会筛选素数

Sieve of Eratosthenes will not sieve Prime Numbers

java

for-loop

sieve-of-eratosthenes