素数を算出するという行為は、何の役に立つのかと考えてみた。
一般的には、暗号処理の因数分解に利用されるようですが、素数の性質は「それ以上割り切れない数」です。
ということは、因数分解できない数字として、唯一のユニーク値という扱いができます。
そもそも、人間の頭で暗算して素数を表すのはせいぜい２桁ぐらいが限界でしょう。
インド式計算なら３桁ぐらいいけるかもしれませんが、713の因数分解を求められたら、頭だけで行うのは結構骨が折れると思います。
やはりコンピュータでそれがさくっと行えるという事は、人が計算機を簡単に使うのと同じで、因数分解を手早く行えるためのアルゴリズムと言えます。
え？因数分解を通常の生活で求められる事が無い？
世の中の出来事を数値で表そうとするプログラミングに興味がなければ、当然そうなのかもしれませんね。
要するに数字に対して興味があるかどうかの違いかもしれませんね。
というわけで、素数を算出するという行為は、パズルを解くという感覚になれるかどうかではないでしょうか？
ソースコード
function getPrimeNumber(num){
flg=0;
for(j=2; j<num-1; j++){
if( num%j == 0 ){
flg=j;
break;
}
}
return flg;
}
{
for(i=2; i<=$1; i++){
if( getPrimeNumber(i) == 0 ){
print i;
}
}
}
実行
$ time echo 100 | awk -f prime_number.awk
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
real 0m0.006s
user 0m0.000s
sys 0m0.000s
AWKは非常に処理速度が早い。
100までの素数は0.006s
1000までの素数で、0.019s
10000までの素数では、0.538s
100000までの素数は、22.629s
素数算出の性質上、値が増えると、累積して計算が増えるため、べき乗での速度がかかる結果になることがわかる。
もしかしたら、もっと孤立的なアルゴリズムがあるのかもしれないが・・・
解説
最大数値をコマンドで指定
AWKの性質上、何かの値を与えてそれを処理するというプログラムフローにしなければいけないので、今回はechoで1からnまでのnの部分を指定するようにしておいた。
指定がない場合はデフォルトで100とかの処理をいれておいてもいいが、今回はさほど問題にならないので、ストレートな仕様にしておいた。
awkの結果表示
配列として取得せずに、レコード単位で値を出力しておくと、数を数える時は
$ echo 100|awk -f prime_number.awk|wc -l
とすればいいので、非常に扱いは楽になるはず。
ただし、内部関数でさらにつなげたい時は、今回の結果をさらに配列に入れ込むようにしましょう。
リンク
色々なプログラム言語でアルゴリズム学習
0 件のコメント:
コメントを投稿