Perlでエラトステネスの篩(ふるい)を用いる。

開発環境はWindows 7 Professional(32bit)+Perl 5.24.0。

エラトステネスの篩(ふるい)とは素数を求めるアルゴリズムです。素数を入れる配列を用意して、最初は無条件に2を入れて、次に、現在の値に対して、素数を入れた配列の要素で次々と割っていき、1回も割れなければ、素数として、配列に新たに追加します。

これを繰り返すことで、ある数までの素数を導き出します。
後になればなるほど、配列の要素数がどんどん増えていくので、素数かどうか導き出すまでに時間がかかります。

今回は、100までの素数をすべて表示するプログラムを作りました。

use strict;
use warnings;

my $num = 100;

my @arr = ();

my $flug = 1;

for(my $i = 2; $i <= $num; $i++){

	$flug = 1;

	if($i == 2){
		print $i." ";
		push(@arr, $i);
	}
		for(my $j = 0; $j < @arr; $j++){

			# 1回でも割れたらアウト
			if($i % $arr[$j] == 0){
				$flug = 0;
				last;
			}

		}

		if($flug){
				print $i." ";
				push(@arr, $i);
		}
}

素数の個数を調べてみると、
10までに4個
100までに25個
1000までに168個
10000までに1229個
100000までに9552個
と、どんどん全体の内の比率が小さくなっていきます。