素数を求める

今日は素数の日。

現在の対象nが素数か判定するのに、以前に求めた素数のリストでひたすら割って確かめる力技。
途中で、ループは半分で良いことに気が付いて修正しました。

my @prime_numbers = &get_prime(shift);
print "@prime_numbers\n";

# &get_prime( n );
#   -> prime number until n.
sub get_prime {
    my ( @prime_numbers ) = 2;
    my $n = shift;

    # auto flash
    $| = 1;

    PRIME: for my $i ( 2..$n ) {
        # print progress status / 10%
        #print '.' unless ( $i % ( $n / 10 ) );
        for ( 0..( $#prime_numbers / 2 ) ){
            next PRIME unless ( $i % $prime_numbers[$_] );
        }
        push @prime_numbers, $i;
    }
    return @prime_numbers;
}

結果
prime2.plが総当りで試していて、prime3.plが半分だけ試している。

% date; ./prime2.pl 100000 > temp; date
Sun Nov 25 00:35:02     2007
Sun Nov 25 00:35:18     2007
% date; ./prime3.pl 100000 > temp2; date
Sun Nov 25 00:35:28     2007
Sun Nov 25 00:35:36     2007
% diff temp temp2
%

16secが8secになったので単純に２分の１。結果も正しいようです。

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 ...