メインビジュアル

CLUB NEWS一覧

HOME > CLUB NEWS > 素数の列を作る

  • CLUB NEWS一覧

理工学部

2011.07.23

理工学部

素数の列を作る

Excelのマクロを使って素数の列を作成してみました。

素数とは1とその数自身以外に正の約数を持たない数の事です。
例えば2や3,5,7,11,13..等が素数です。
素数でない数は2つ以上の素数の積で表せるので合成数といわれています。例えば6=2×3と表せますね。

さて、素数は無限に存在する事が知られています。小さいほうから素数をいくら列挙しても終わりはありません。
というわけでとりあえず小さいほうから1万個目まで求めてみました。

当然手計算では無理(出来なくは無いでしょうが、とてつもなく時間がかかるので現実的ではありません)なので、Excelのマクロを使いました。

アルゴリズムは単純で2以外の素数は全て奇数(2以外の偶数は2を約数にもつので合成数です)なので...
・3以上の奇数について、既に発見した素数で割れるかを小さい素数から順に確認していく
・調べようとしている奇数が、既知の素数で割り切れたら、その数は合成数だったとわかる
・既に発見されていた素数で割る事が出来なければ新たな素数として列に追加する
という流れです。
既知の素数での確認する部分は、全ての素数で試す必要はありません。いま調べようとしている奇数の平方根より小さな素数についてだけ確認すれば十分です。こうする事で計算回数を節約出来るので実行時間が短縮出来ます。

さて、実行結果ですが...
1万個目の素数は「104729」でした。

計算時間はコンピューターの性能やExcelのバージョン等によって変わるので今回使用したものを載せておきます。

OS:MacOS X 10.7
Excel:Microsoft Excel for Mac 2011(バージョン14.1.2)
CPU:Intel core 2 Duo 2.93GHz
MM:4GB

1万個の素数を求めるのにかかった時間は30秒ほどでした。

でき上がった素数の列をみていると...何だか不思議な気分になります。10000個だしてはみましたが無限に存在する素数のごく一部にすぎません。もちろんたとえ数百億個もとめようがそれは「ごく一部」なわけですが...。

今度はもっと沢山の素数を求めていろいろ調べてみたいと思います。

CLUB NEWSカテゴリ

すべてのCLUB NEWS

体育部

文化部

同好会

サークル

アーカイブ