素数を求める

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

• 2015年06月03日 11:44
• 渡辺隆行

アルゴリズムの概要

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

計算

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

（注：ページを再読込すると計算結果がクリアされます．）

結果： ここに素数だけが表示されるよ！

© Takayuki Watanabe