素数判定

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も効かないので電源を切った。

時刻:
ラベル: