埃拉托斯特尼筛不出素数

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开始打印出来，问题似乎是在我将数组初始化为true后，它没有将合数标记为false。

提前感谢你的帮助。

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;
}