2

我从伪代码用 Java 实现了 Eratosthenes 筛：

public static void sieveofEratosthenes(int n) {
    boolean numArray[];

    numArray = new boolean[n];
    for(int i = 0; i < n; i++)
        numArray[i] = true;

    int a = 0;

    for(int i = 2; i < Math.sqrt((double)n); i++) {
        if(numArray[i])  {
            for(int j = (int)Math.pow(i, 2); j < n; a++) {
                numArray[j] = false;
                j += (a * i);
            }
        }
    }

    for(int i = 2; i < n; i++) {
        if(numArray[i])
            System.out.println(i);
    }
}

当我是 15 时，它给我的输出：

2
3
5
7
8
11
12
13
14

为什么其中一些值不正确？我相信我的错误在于我如何定义和使用 bool 数组。谢谢！

4

4 回答 4

4 
        for(int j = (int)Math.pow(i, 2); j < n; a++) {
            numArray[j] = false;
            j += (a * i);
        }

应该读

        for(int j = (int)Math.pow(i, 2); j < n; j+=i) {
            numArray[j] = false;
        }
于 2014-08-22T04:50:24.343 回答
2

SoE 的工作原理是它获取每个数字并“删除”它后面的所有可被它整除的数字。所以基本上每个数字x + k*x其中k > 0。这可以通过简单地将x添加到初始x^2然后迭代地添加x来完成。这里：

for(int j = (int)Math.pow(i, 2); j < n; a++) {
    numArray[j] = false;
    j += (a * i);
}

您没有添加x而是a*x ，因此您将在a递增时跳过一些数字（因此您将删除 4,6,10,16 等，看到模式吗？它会在初始值中添加 2,4,6 等值）所以你应该坚持：

for(int j = (int)Math.pow(i, 2); j < n; j+=i) {
    numArray[j] = false;
}
于 2014-08-22T04:57:04.890 回答
0

问题出在一线

 j += (a * i);

在循环中，此语句逐渐将 j 乘以 a*i并将其与 j 相加。因此将上面的行替换为，

 j = (a * i);

它会起作用的。是的，初始化

a=2

因为我们不希望 numarray[0] 或 numarray[1] 初始化或使用。如果有任何疑问，请发表评论。谢谢

于 2014-08-22T05:12:07.023 回答
0

这并不能直接解决您的问题，但由于它已经得到回答，我认为重复它没有任何意义。但是，查看您的代码，我建议使用整数乘法而不是Math.pow并Math.sqrt获得更好的性能，例如：

for(int i = 2; i*i < n; i++) {
    if(numArray[i])  {
        for(int j = i*i; j < n; j += i) {
            numArray[j] = false;
        }
    }
}

诚然，每次外循环迭代只会进行一次这些调用，因此改进可能不是很显着。但是，调用Math.pow和Math.sqrt可能比单个整数乘法计算密集得多。此外，如果 Java 执行足够复杂的优化，i*i可能只计算一次并在两个地方使用，从而节省更多的计算周期。在这种情况下也没有整数溢出的风险，因为i*i上面是整数n。

于 2014-08-22T16:48:08.970 回答