追記〜perlで素数を表示する

最近ひたすらperlのOOPを学んでいる今日この頃。
なんか委託先の人とかってやっぱりコードがすごく綺麗で、
「LL結構かけますよー」
なんてさらって言うためにとっかかりに歴史の古いperlを。
ある程度書けるようになったらrubyやらjavascriptやらもうちょっと
掘り下げて勉強していく予定です。
#仮想テナント構築が止まっているのは仕様です。

さてさて、N個目の素数を表示するコードを書く機会があったので書いてみたのです。
素数そのものの記憶がなかなか怪しくてとっかかり苦労しましたが、
なんとか形になった模様です。。

#! /bin/perl -w
#引数取得
$hiki=$ARGV[0];
$hiki =~ /[^0-9]+|^$|^0/ and die "input data is please number!\n";

#変数定義
$filename="./sosu_cache.txt";

my $sosu=2;
my $flg=0;
my $scnt=0;
my $fcnt=1;
my $h=();

#キャッシュファイルの読み込み
if(-f $filename){
	open IN,$filename;
	while(<in>){
		chomp;
		$h-&gt;{$fcnt}=$_;
		$fcnt++;
	}
	close IN;
}else{
	$h-&gt;{1}=2;
}
#キャッシュに存在すれば回答して終了
print "$hiki個目の素数は$h-&gt;{$hiki}\n" and exit if($h-&gt;{$hiki});</in>

#キャッシュファイルを追記モードでオープン
open OUT,"&gt;&gt; $filename" or die "can't open cache file!";

#キャッシュが存在すれば
if($h-&gt;{1}){
	$knt= keys $h;
	if($knt==1){
		print OUT "2\n";
		$sosu=3;
	}else{
		$sosu=$h-&gt;{$knt}+2;
	}
	$scnt=$knt;
}
while(1){
	#対象の数字以外で割り切れるか確認
	for($i=2;$i&lt;$sosu;$i++){
		if($sosu%$i==0){
			$flg++;
			last;
		}
	}
	#素数ならば
	if($flg==0){
		$scnt++;
		print OUT "$sosu\n" unless($h-&gt;{$scnt});
		if($scnt==$hiki){
			print "$hiki個目の素数は$sosu\n";
			close OUT;
			exit;
		}
	}
	#インクリメント
	$sosu+=2;
	$flg=0;
}

基本的には存在しうる素数を指定されたN個まで計算するロジック。
ただ引数に10000とか与えられるとちょっと動きが重いので、
キャッシュ出来るようにしてみたにだ。


[~]$time perl primenumber.pl 5000
5000個目の素数は48611

real	0m16.214s
user	0m16.178s
sys	0m0.017s
[~]$time perl primenumber.pl 5000
5000個目の素数は48611

real	0m0.015s
user	0m0.009s
sys	0m0.005s

追記
意外とアクセスが有ったりする記事で、ちょっとダサかったので
リファクタリングしました。。。
※これまで大学の授業とかでコピペした人ごめんなさい。

#! /bin/perl -w
use warnings;
use strict;
use utf8;
binmode(STDOUT, ":utf8");
#引数取得
my $hiki=$ARGV[0];
$hiki =~ /[^0-9]+|^$|^0/ and die "input data is please number!\n";

#素数結果配列
my @s=(2,3);

#素数処理用一時変数
my $pnum=3;

#無限ループさせる
ROOT:while(1){
        #処理する素数候補
        $pnum+=2;

        #これまでの素数で割り切れたら次のループへ
        for(@s){
                next ROOT if($pnum % $_ == 0);
        }

        #割り切れなければ
        push @s,$pnum;

        if(defined($s[$hiki-1])){
                print $hiki . "個目の素数は" . $s[$hiki-1] . "\n";
                exit;
        }
}

キャッシュ機能を省いて、割り切れる数字を探す処理もこれまでの素数としました。
だいぶ速度も改善されてると思います。


[learn_perl]$time perl sosu.pl 5000
5000個目の素数は48611

real	0m1.081s
user	0m1.072s
sys	0m0.007s

共有:

いいね: