素数を列挙する

Haskellだと遅延評価で素数列に限らず「無限列なんでも来い」ですが，Perlだとどうなるでしょう．ここはMJD師匠（勝手に師匠よばわり）のHigher-Order Perlに助けを求めます．

Perlでの「遅延評価」はコードリファレンス（サブルーチンへのリファレンス）とクロージャの組合せでイテレータを作ってなんとかするのがHigher-Order Perlの四章の極意（と勝手に解釈）．

Project EulerのProblem 7をPerlで解いてみます（追記2008/4/9：無駄な処理を修正しましたと思ったら，余計に無駄だった・・・）．

use strict;
use warnings;

sub primefactory{
    my @primes=(2,3);
    my $state=-1;
    return sub{
        $state++;
        return $primes[$state] if $state==0 or $state==1;
        my $prime_cand=$primes[-1]+2;## +1; 素数+1は素数にならないので+2でよい
        SIEVE:
        ##foreach my $d ( @primes ){##逆に無駄
        foreach my $d (2 .. int(sqrt($prime_cand))+1){##ここに無駄が多い
            if ($prime_cand % $d ==0){
                $prime_cand++;
                goto SIEVE; 
            }
        }
        @primes=(@primes,$prime_cand);
        return $primes[-1];
    }
}

my $x=primefactory();
foreach (1..10000){$x->()}
print $x->(),"\n"

エラトステネスの篩なので実行速度はそれなりですが，これで素数列が得られますし，答えの104743も得られます．きちんとオブジェクトにすればいろいろ機能をつけられるのでしょうが，それは後回し．

篩の部分にも無駄が多すぎで，そもそもすでに得られた素数列を使うべきですが，それも後回し(^^;;少し効率化しました．と思ったら，逆効果だった．判別そのものが時間を費やすようです．