素数を求める

「エラトステネスのふるい」というアルゴリズムを用いて,2からnまでの範囲で素数(1とそれ自身でしか割り切れない数)を求めます.HTMLのFormで値を入力し,JavaScriptの関数で計算し,HTMLのDOMを操作して結果を動的にHTMLに挿入しています.(つまり,インタラクティブなUIの例)

アルゴリズムの概要

  1. まず,2からnまでの数字全部を「素数候補」としておく.
  2. 2は素数である.
  3. 2の倍数は素数ではないので,「素数候補」のマークを外す.
  4. 2の次の数字iが「素数候補」でないならば,その次の数字に移動.
  5. 2の次の数字iが「素数候補」ならば(今の場合はi=3だからこちらに該当),iの倍数は素数でないから,「素数候補」のマークを外す.
  6. 以下,nの平方根に至るまで,iの次の数字に対して同じ操作を繰り返す.
  7. 「素数候補」に残った数字が素数.

計算

素数を求める範囲として,3以上10000以下の数を指定してください.

素数を求める範囲(n):

(注:ページを再読込すると計算結果がクリアされます.)


結果: ここに素数だけが表示されるよ!


クリエイティブ・コモンズ・ライセンス© Takayuki Watanabe