N88-BASICで素数 (1回目)
2021/11/26(金)
N88-BASICで素数 (1回目)
1～10000までの1229個の素数を求める
(NL-BASICはAlt+6で高速化)
エラトステネスのふるい(Sieve of Eratosthenes)
1は素数ではないので消します
(素因数分解は6=2×3で6=1×2×3ではない)
2は素数なので2より大きい2の倍数を消す
(消えていない数は素数と判断)
3は素数なので3より大きい3の倍数を消す
4は2の倍数なので消えている(素数でない)
5は素数なので5より大きい5の倍数を消す
…
と[√10000]=100まで繰り返し
残った数が素数です
([x]はガウス記号でxを超えない最大の整数)
b>[√n]、n=b×aとするとb≧aとなり
nはaの倍数としてすでに消えている
つまり[√n]より大きい数の2～n/[√n]倍の数は
すでに消えているということです
通常配列を使うところをグラフィック画面に
点を描いて色で判定しています。
(素数でない場合は0:黒)
100×100(1～10000)のマスに残った素数が
描く模様がどのようなものになるのかと思い
描いてみました
NL-BASICとblg～.zip(prime001.bas)は
このブログ(以下のリンク)から
ダウンロードできます
1～10000までの1229個の素数を求める
(NL-BASICはAlt+6で高速化)
エラトステネスのふるい(Sieve of Eratosthenes)
1は素数ではないので消します
(素因数分解は6=2×3で6=1×2×3ではない)
2は素数なので2より大きい2の倍数を消す
(消えていない数は素数と判断)
3は素数なので3より大きい3の倍数を消す
4は2の倍数なので消えている(素数でない)
5は素数なので5より大きい5の倍数を消す
…
と[√10000]=100まで繰り返し
残った数が素数です
([x]はガウス記号でxを超えない最大の整数)
b>[√n]、n=b×aとするとb≧aとなり
nはaの倍数としてすでに消えている
つまり[√n]より大きい数の2～n/[√n]倍の数は
すでに消えているということです
通常配列を使うところをグラフィック画面に
点を描いて色で判定しています。
(素数でない場合は0:黒)
100×100(1～10000)のマスに残った素数が
描く模様がどのようなものになるのかと思い
描いてみました
NL-BASICとblg～.zip(prime001.bas)は
このブログ(以下のリンク)から
ダウンロードできます
