素数自動育成
何を酔狂な事をと云われそうだが．．．
素数を自動育成するphpを作ってみた。素数を自動で育成するというプログラムは練習用として比較的ポピュラーなケースかも知れないが今回のロジックは自分で組んでみた。フラグを立ててループを制御しているところが難だが割と綺麗なロジックだと思う。今回のソースの中から素数割り出しのコア部分を引用する。
まず、育成する素数の配列$paryに初期値2を入れる。$nを2から一つずつカウントアップする。素数用の配列の中から割り切れる数があったらそれは素数ではない。割り切れなかったら素数配列に格納する。そして、次の数が素数であるかどうかを判定する。素数配列が増えれば増えるほど判定に時間がかかるけど、これは致し方あるまい。
$pary = array(2); //素数配列初期化
$i = 0; //素数配列添字初期化
$flg = FALSE;
for ($n = 2; $n <= $max; $n++){
foreach ($pary as $p){
if ($n % $p == 0){
$flg =TRUE;
break;
}
}
if ($flg){
$flg = FALSE;
continue;
}
$pary[++$i] = $n;
}
正しく計算できている事はこちらのサイトで検証した。全部比較した訳でもないけど何カ所か確認して間違ってるところは無かったので大丈夫だろう。
http://homepage2.nifty.com/hiranouchi/prime/index.html
動作時間を測定するルーチンを組み込み*1ローカルホストで実行してみた。千まで計算するのに0.03秒、一万迄だと1.3秒、二万だと5秒ほど。pentium M 1.4MHz、メモリ512MBでの結果。
作ったのはこちら。
http://yukihiro.z1.bbzone.net/etc1/mathematics.php
または
http://yukihiro.z1.bbzone.net/etc1/mathematics.php?max=1000
maxの値はいくらでも変えられるけど鯖がかわいそうなので今回は一万までとした。
出力結果はテキストに貼り付ければcsvとなるので色々と利用が出来る*2。
俺的にはwwwサーバーとネット回線を用いてこんなどうでも良い計算をするという事になんかロマンを感じる。
あークダラナイ、って自分でも思う。
-
ローカルホストで10万まで計算してみたらタイムアウト（笑）。
5万までで27.57sec。タイムアウトは30秒なのでギリギリだ。Apacheの設定を変えれば計算できるのかな。
5万までの計算結果はこちら。
http://yukihiro.z1.bbzone.net/etc1/prime_numbre_50000.csv
