素数を出力する

レッスンに戻る

1より大きい整数nを、1と自分自身以外で割り切れない場合、素数と呼びます。

言い換えると、n > 1は、1とn以外で割り切れない場合に素数です。

たとえば、5は、2、3、4で割り切れないので素数です。

2からnまでの範囲で素数を出力するコードを書いてください。

n = 10の場合、結果は2,3,5,7になります。

追伸コードは、固定値に合わせて微調整されるのではなく、任意の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 の平方根までの約数を探すこともできます。しかし、とにかく大きな範囲に対して本当に効率よくする場合は、アプローチを変更して、二次ふるい法や一般数体ふるい法などの高度な数学と複雑なアルゴリズムに依存する必要があります。