帰ってきたネコブログ

なぜ、このタイミングで素数を求めるのかアレですが、息抜きです。
勘のイイ人は気付いてるかもしれませんが、
この数列を使って、シェルソートを動かしてみたい訳です。

まずは、素数を求めてみます。

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 = 2..$n;
    while ( @wk ) {
        my $prime = shift @wk;
        @wk = grep { ($_ % $prime); } @wk;
        push @ret, $prime;
    }

    return @ret;
}

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

このアルゴリズムは、「エラトステネスのふるい」というそうです。(*1)
見ての通り、小さい方から素数を確定して、
その素数で割り切れる数字を取り除いて、
この繰り返しで計算しています。

今回は、「余り」を求めて、grepで除去していますが、
他の方法もあるので、次回はそっちも実装して、
処理時間を比較してみようと思います。

おしまい。

(*1) 自分の解釈で書いてるので、おかしいことになってたらゴメンなさい。

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