0

10,001番目の素数を見つけようとしています。他の人が書いたコードを見たことがありますが、それが何を意味するのかよくわかりません。エラトステネスのふるいを使用しようとしたコードを JavaScript で書きました。何が問題なのかわからない。正しく動作するはずですが、間違った答えが得られます。

var compute = function() {
var prime = [2,3,5,7,11,13,17,19];
for(var i=20; i<=80000;i++) {
if(i%2!==0 && i%3!==0 && i%5!==0 && i%7!==0 && i%11!==0 && i%13!==0 && i%17!==0 &&      i%19!==0) {
 prime.push(i);
  }
 }  
 console.log(prime[10000]);
};

 compute();
4

2 に答える 2

2

あなたのコードはエラトステネスのふるいを実装していません。次の手順を実装する必要があります (ソース: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes )。

  1. 2 から n までの連続する整数のリストを作成します: (2, 3, 4, ..., n)。
  2. 最初に、p を最初の素数である 2 とします。
  3. p から始めて、p の増分でカウントアップし、リスト内の p 自体よりも大きいこれらの数値のそれぞれにマークを付けます。これらは p の倍数になります: 2p、3p、4p など。それらのいくつかはすでにマークされている可能性があることに注意してください。
  4. マークされていないリストで p より大きい最初の数を見つけます。そのような数がなかった場合は、停止します。それ以外の場合は、p をこの数 (次の素数) に等しくし、手順 3 から繰り返します。

10001 番目の素数を見つけたい場合は、十分な大きさの n を選択して、結果の配列に少なくとも 10001 要素が含まれるようにし、結果として 10001 番目の要素を選択する必要があります。

于 2013-04-18T04:17:07.643 に答える