素数判定

1億より小さい素数は5761455個あり、それをすべて表示するのにかかった時間は約3時間16分だった。

「エラトステネスのふるい」方式の改良版。

1千万までで1分かからなくなった。

これで1億までやってみる。

VPSでやろうとしたら Out of memoryになったので、10GBのメモリがあるWindows7でやる。

use strict;
use warnings;
my @array =();
my @new_array =();
my $max = shift || 1000;
open my $result, '>', 'result.txt' or die;
my $start_time = localtime();
my $count=0;
for(0..$max-1){
    push @array, $count;
    $count++;
}
$array[1] = 0;
for(my $i=2;$i
    for(my $j=$i*2;$j<=$#array;$j=$j+$i){
        $array[$j] = 0;
    }
}
$count = 0;
for(@array){
    if($_>0){
        $count++;
        print $result "$_\t";
    }
}
print $result "\nTo $max count :  $count \n";
my $end_time = localtime();
print $result "$start_time - $end_time\n";
close $result;

6分弱で終わった。5761455個。1億より小さい最大の素数は 99999989 である。

あるページのこの表をあんまり頻繁にみるので自分のところに書く。

範囲 素数の個数

10以下 4

100以下 25

1000以下 168

1万以下 1229

10万以下 9592

100万以下 78498

1000万以下 664579

1億以下 5761455

10億以下 50847534

100億以下 455052511

1000億以下 4118054813

1兆以下 37607912018

10兆以下 346065536839

10億までやろうとしたらパソコンがハンブアップした。ctrl+alt+deleteも効かないので電源を切った。