Java: Sieve of Eratosthenes:数组作为参数

Question

我的目标是关闭或设置为false，所有不是质数的阵列点。数组是作为参数提供的。

public static boolean[] sieveOfEratosthenes(boolean [] a){

    int increment= 2;

    for(int n = 0; n < 9; n++){
        for(int i = increment; i < a.length; i += increment){
            a[i] = false;
        }
        increment += 1;
    }   
    a[2] = true;
    a[3] = true;
    a[5] = true;
    a[7] = true;
    return a;
}

代码运行得很好，我只是想知道是否有比使用更有效的方法：

a[2] = true;
a[3] = true;
a[5] = true;
a[7] = true;

将这些数组项重置为true。

提前感谢！

Answer 1

这样做的一个好方法是从迭代* 2开始循环。

int increment= 2;

for(int n = 0; n < 9; n++){
    for(int i = increment*2; i < a.length; i += increment){
        a[i] = false;
    }
    increment += 1;
}  

这样，您就可以跳过第一个。

其次，修改您的外部循环，使其忽略已经为false的值，因为它的主因子处理了它的乘积。现在你的循环看起来像这样

int increment= 2;

for(int n = 0; n < 9; n++){
    if(a[increment]) {
      for(int i = increment*2; i < a.length; i += increment){
          a[i] = false;
      }
      increment += 1;
    }
}

第三，处理数组中任意大小的数组循环以获取增量值

int count = a.length;

for(int increment = 2; increment < count; increment++){
    if(a[increment]) {
      for(int i = increment*2; i < count; i += increment){
          a[i] = false;
      }          
    }
}

这个电流回路假设1和0是质数。因此，设置a[0] = a[1] = false;以反映0和1不是质数的事实。