1

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

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;

将这些数组项重置为真。

提前致谢！

4

1 回答 1

2

一个好方法是在迭代 * 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;
}

这样你就跳过了第一个。

其次修改您的外部循环，使其忽略已经为假的值，因为它的主要因素照顾了它的产品。现在你的循环看起来像这样

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 不是素数的事实。

于 2012-08-31T21:42:51.917 回答