100までの整数から素数を列挙せよ

流行のお題に挑戦してみます。他の方の回答を見ずに、自分で書いてみました。配列を使って、エラトステネスの篩をかけています。恐らく定番の方法だとは思いますが、自分で思いつく一番“Perl っぽい”回答です。(^_^)


use strict;
 
sub find_primes($) {
  my ($max) = @_;
  my @numbers = (2..$max);
  my @primes = ();
 
  while(@numbers) {
    my $n = shift @numbers;
    push @primes, $n;
    @numbers = grep $_ % $n, @numbers;
  }
  return @primes;
}
 
print join " ", find_primes(100);

まず範囲構文を使って、2から引数までの数列 @numbers を作ります。
@numbers の先頭は素数とみなし、@primes に push します。そして、grep を使って割り切れる数を除いた数列を新たに @numbers にセットします。$_ % $n （余り）が 0 になると偽になるので除外されるわけです。
これを @numbers が空になるまで繰り返すと、@primes に素数が集まるはずです。
実行結果は以下の通り。

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

ちなみに、find_primes(10000) と大きな数をとると1秒程度かかりました。

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 101 103 1
07 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 2
23 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 3
（中略）
49 9661 9677 9679 9689 9697 9719 9721 9733 9739 9743 9749 9767 9769 9781 9787 97
91 9803 9811 9817 9829 9833 9839 9851 9857 9859 9871 9883 9887 9901 9907 9923 99
29 9931 9941 9949 9967 9973

考えた事が思ったように動くと、楽しいですね。(^_^)

追記高速版

上の方法だと 1,000,000 などの大きな数ではとても時間がかかってしまうので、速いバージョンも作ってみました。平方根を使っています。


use strict;
 
sub find_primes($) {
  my ($max) = @_;
  my @primes = ();
 
  for (my $i = 2; $i <= $max; $i++) {
    my $im = int(sqrt($i) + 1);
    my $is_prime = 1;
    for my $p (@primes) {
      last if $p >= $im;
      if ($i % $p == 0) {
        $is_prime = 0;
        last;
      }
    }
    push @primes, $i if $is_prime;
  }
 
  return @primes;
}
 
print join " ", find_primes(1000000);

うちの環境（Athlon 64 2.4GHz）では 10 秒程度で表示されます。join や print しなければ 6 秒程度でした。やはり単純な方法が一番速いですね。

追記 高速版

追記高速版