素数の出力

レッスンに戻る

1 よりも大きい整数で、1 と自身以外では、余りなく割ることができない場合、その数値は素数(prime) と呼ばれます。

つまり、1より大きいnが 1 と n 以外では割り切れない場合、素数となります。

例えば、5 は素数です。なぜなら、2, 3 と 4 ではあまり無く割ることができなからです。

2 から n の範囲で、素数を出力するコードを書きなさい。

n = 10 の場合、結果は 2,3,5,7 です。

P.S. コードは任意の n で動作させてください。固定値でハードコードはしないでください。

このタスクを解決するのに、多くのアルゴリズムがあります。

入れ子ループを使ってみましょう:

          For each i in the interval {
  check if i has a divisor from 1..i
  if yes => the value is not a prime
  if no => the value is a prime, show it
}
        

ラベルを使ったコードです。:

let n = 10;

nextPrime:
for (let i = 2; i <= n; i++) { // for each i...

  for (let j = 2; j < i; j++) { // look for a divisor..
    if (i % j == 0) continue nextPrime; // not a prime, go next i
  }

  alert( i ); // a prime
}

ここには最適化の余地が沢山あります。例えば、2 から i の平方根までの約数を探すことができます。しかし、とにかく、私たちが大きな間隔に対して効率的になりたいなら、アプローチを変更し、高度な数学とQuadratic sieve, General number field sieveなどの複雑なアルゴリズムに頼る必要があります。