Perl で素数生成
意外と知られていないですが、n番目の素数を与える式は存在します。それを使って、素数を求めるプログラムを Perl で組んでみました。公式はここで与えられた式を使ってみました。1番目から9番目の素数を求めてみたのですが、以下のようになりました。
非常に素朴に式をそのまま Perl で組んだので、ご覧のとおり、7番目までしか求まっておらず、あとはエラーになっています。計算のどこかで大変大きな数が出てきたか何かで、もっと工夫しないとダメですね。これなら「エラトステネスの篩」の方が簡単で大きな素数が扱えそうです。
コードは以下です。
use strict; use warnings; $| = 1; for my $i (1..9) { print &p( $i ).", "; } sub p { my $n = $_[0]; my $num = 1; for ( my $m = 1; $m <= 2 ** $n; $m++) { $num += int( int( $n / &mh( $m ) ) ** ( 1 / $n ) ); } return $num; } sub mh { my $na = 0; for ( my $k = 1; $k <= $_[0]; $k++ ) { $na += int( ( &factorial( $k-1 ) +1 ) / $k - int( &factorial( $k-1 ) / $k ) ); } return $na; } sub factorial { my $j = 1; for ( my $i = 1; $i <= $_[0]; $i++) { $j *= $i; } return $j; }