帰ってきたネコブログ

前回とは異なる方法で、
「エラトステネスのふるい」を実装しようと思います。

use strict;
use warnings;
use v5.10;

die 'Usage: perl aaa.pl <integer>' if scalar(@ARGV) == 0;
my @prime = calc_prime( $ARGV[0] );

while ( @prime ) {
    for ( 1..10 ) {
        printf( "%4d", shift @prime );
        if ( 0 < scalar(@prime) ) {
            print ',';
        }
        else {
            last;
        }
    }

    print "\n";
}

sub calc_prime {
    my $n = shift;

    my @ret = ();
    if ( $n < 2 ) {
        return @ret;
    }

    my @wk = 0..$n;
    $wk[0] = -1;
    $wk[1] = -1;

    for (my $i=0; $i<=$n; $i++) {
        next if $wk[$i] < 0;

        for (my $j=($i+$i); $j<=$n; $j+=$i) {
            $wk[$j] = -1;
        }
    }

    return grep { $_ != -1; } @wk;
}

実行するとこんな感じ。
$ perl aaa.pl 100
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

見つかった素数で割り切れる値を配列から省く代わりに、
添え字が素数の倍数の要素に計算除外マークを付けて、
マークの付いてない数字を素数として返しています。

で、本当は、前回の実装と処理時間を比較しようと思ったのですが、
今回の実装だと、引数に100000を指定してもサクッと終わってしまい、
体感で分かるくらい早くなったので、
まずは、前回の実装を見直してから比較しようと思います。

おしまい。

カテゴリー: Perl, コンピューター by ネコ on 2013年09月15日 | タグ: アルゴリズム > メモ > 素数