使用埃拉托色尼筛法检查列表中的素数

Question

我有一个数组作为输入，我想打印该列表中存在的素数。我能够使用 trial division method 做到这一点。但是我在尝试使用 Eratosthenes method 的筛子做同样的事情时感到震惊。

我尝试使用以下代码，但对如何将最终结果数组与我的输入数组列表进行比较以及 return 仅与输入列表匹配的那些值感到困惑。（作为 javascript 的初学者，详细的回答会有所帮助）。

var arr=[4,7,10,12,13,19,22,37];
function checkPrime(arr)
{
  var output=[],primes=[];
  var x=arr.length;
  for(i=2;i<=arr[x-1];i++)
    primes[i]=1;

  for(i=2;i<=arr[x-1];i++)
    for(j=2;j<=Math.sqrt(arr[x-1]);j++)
      primes[i*j]=0;


  for(i=0;i<=arr[x-1];i++){
    if(primes[i]==1){
      output.push(i);
     }
    }



  return output;
}

console.log(checkPrime(arr));

Answer 1

创建输出列表时，您想与 arr 中的值进行比较，而不是索引，因此您需要将 primes[i] 替换为 primes[arr[i]]。

所以这个：

if (primes[i] == 1) {
  output.push(i);
}

变成这样：

if (primes[arr[i]] == 1) {
  output.push(arr[i]);
}

使用埃拉托色尼筛法检查列表中的素数

Check for prime in a list using sieve of Eratosthenes

javascript

algorithm

data-structures