java - Eratosthenes 筛法不会筛选素数

Question

对于我正在为我的一个类(class)做的作业，我们必须实现埃拉托色尼筛法。我已经尝试了七次来获得一个有效的代码，并尝试合并我研究过的众多解决方案。我终于有了一个可以输出数字的。不幸的是，它会同时打印合数和质数，但不会打印 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；这就是 max = composite 的原因.size() 靠近顶部)
• 明确地将 2、3 移开，然后
• 依赖于所有大于 3 的素数都等于 1 或 5 mod 6 的事实；这就是最终循环在加 2 和 4 之间交替的原因

它返回一个 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;
}