素数を求める（４）
次は、2つの方式の速度比較。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | use strict;use warnings;use v5.10;use Benchmark qw/cmpthese/;die 'Usage: perl aaa.pl <integer>' if scalar(@ARGV) == 0;my $max_num = $ARGV[0];cmpthese( 10, { 'calc1' => sub { my @prime = calc_prime1( $max_num ); }, 'calc2' => sub { my @prime = calc_prime2( $max_num ); }} );sub calc_prime1 { 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; my $prime = $wk[$i]; for (my $j=$i+1; $j<=$n; $j++) { next if $wk[$j] < 0; if ( ($wk[$j] % $prime) == 0 ) { $wk[$j] = -1; } } } return grep { $_ != -1; } @wk;}sub calc_prime2 { 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 10000 (warning: too few iterations for a reliable count) s/iter calc1 calc2calc1 1.89 -- -99%calc2 1.00e-02 18760% -- |
分かってはいたんですけどね、体感で違い過ぎたので。
ただ、添え字でどうこうするのは、
大きな素数を計算するのには向かない気がするので、
その場合は時間が掛かってでも、
すでに見つかった素数で余りを計算する方が現実的な気がします。
でも、そこはSSDを使えば、もっと早く計算できたりするんですかね。
という訳で、素数の計算はここまで。
おしまい。
Leave a Comment