読者です 読者をやめる 読者になる 読者になる

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;
}