2006年06月16日 22:00 [Edit]

perl - 100までの素数

LLR2006

なに前哨戦とな?

キミならどう書く 2.0 - ROUND 1 - ? Lightweight Language Ring
お題は「100までの整数から素数を列挙せよ」です.

まずはCPANから。Perlから、と言わないところがミソ。

perl -MMath::Prime::XS=primes -le '$,=" "; print primes(100)'

primessieve_primesとするとさらに高速。$,の使い方にも注目。

次にabigailの傑作の変種。

perl -le '$,=" "; print grep { (1 x $_) !~ /^(11+)\1+$/ } (2..100)'

なんでこれで素数判定できるかは、読者の宿題。

最後に、割とけれんみのない実装。なるべくPerlっぽくしてみた。

use strict;
use warnings;
my @primes;
sub is_prime{
    my $n = shift;
    for my $d (@primes){
        last if $d*$d > $n;
        return unless $n % $d;
    }
    push @primes, $n;
    return $n;
}
my $max = shift || 100;
is_prime($_) for (2 .. $max);
print join(" ", @primes), "\n";
__END__
革命の日々! カーネル読書会で発表してきました
57は素数ですが何か?

kosakiさんの傷に塩をすり込むテスト。

% perl primes.pl | grep 57
% perl primes.pl | grep 97
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
%

ん、まてよ、ひょっとしてoctal?

% perl -le 'print 057'
47
% perl primes.pl | grep `perl -le 'print 057'`
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
%

塩を塗るつもりが塩を送ってしまった。

Dan the Prime Perl Monger


この記事へのトラックバックURL

この記事へのトラックバック
素数系の問題でウケを取るときはエラトステネスのふるいを使うのが定番だよなーと思いつつ考えてみた。 あー、これって と書き換えたら、後は簡単に分かるな。 (pp)の1回以上の繰り返しで2の倍数が消える。 (ppp)の1回以上の繰り返しで3の倍数が消える。 (pppp)の1回以上の...
[math]「なんでこれで素数判定できるかは、読者の宿題」【otsune's SnakeOil】at 2006年06月17日 03:45
この記事へのコメント
3X19=57 ヽ( ´¬`)ノ
Posted by れもね at 2006年06月20日 10:37
((((;゚Д゚)))ガクガクブルブル
Posted by kosaki at 2006年06月17日 20:36