[アルゴリズム] 1から100までの素数を取得(AWK編)

board-935455_1280
LINEで送る
Share on GREE
Share on LinkedIn

素数を算出するという行為は、何の役に立つのかと考えてみた。
一般的には、暗号処理の因数分解に利用されるようですが、素数の性質は「それ以上割り切れない数」です。
ということは、因数分解できない数字として、唯一のユニーク値という扱いができます。
そもそも、人間の頭で暗算して素数を表すのはせいぜい2桁ぐらいが限界でしょう。
インド式計算なら3桁ぐらいいけるかもしれませんが、713の因数分解を求められたら、頭だけで行うのは結構骨が折れると思います。
やはりコンピュータでそれがさくっと行えるという事は、人が計算機を簡単に使うのと同じで、因数分解を手早く行えるためのアルゴリズムと言えます。
え?因数分解を通常の生活で求められる事が無い?
世の中の出来事を数値で表そうとするプログラミングに興味がなければ、当然そうなのかもしれませんね。
要するに数字に対して興味があるかどうかの違いかもしれませんね。
というわけで、素数を算出するという行為は、パズルを解くという感覚になれるかどうかではないでしょうか?

ソースコード

実行

AWKは非常に処理速度が早い。
100までの素数は0.006s
1000までの素数で、0.019s
10000までの素数では、0.538s
100000までの素数は、22.629s
素数算出の性質上、値が増えると、累積して計算が増えるため、べき乗での速度がかかる結果になることがわかる。
もしかしたら、もっと孤立的なアルゴリズムがあるのかもしれないが・・・

解説

最大数値をコマンドで指定

AWKの性質上、何かの値を与えてそれを処理するというプログラムフローにしなければいけないので、今回はechoで1からnまでのnの部分を指定するようにしておいた。
指定がない場合はデフォルトで100とかの処理をいれておいてもいいが、今回はさほど問題にならないので、ストレートな仕様にしておいた。

awkの結果表示

配列として取得せずに、レコード単位で値を出力しておくと、数を数える時は

とすればいいので、非常に扱いは楽になるはず。
ただし、内部関数でさらにつなげたい時は、今回の結果をさらに配列に入れ込むようにしましょう。

リンク

素数計算プログラム

Javascript
PHP
Python
Shell
AWK

アルゴリズム過去記事

http://wordpress.ideacompo.com/?cat=562&tag=Algorithm

Leave a Reply

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です


*