Problem 10

素数関係なので着手．

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

訳

10未満の素数の和は2 + 3 + 5 + 7 = 17.

2,000,000未満のすべての素数の和を求めよ．

[Haskell] 前に考えたものをそのまま流用

primes::[Integer]
primes=2:3:([6,12..] >>= (\x ->(g (x-1))++(g (x+1))))

takeLeThanSqrt::Integer -> [Integer]-> [Integer]
takeLeThanSqrt y xs = takeWhile (\x -> leThanSqrt x y) xs

leThanSqrt::Integer -> Integer -> Bool
leThanSqrt x y = (fromInteger x) <= (sqrt $ fromInteger y )

g::Integer->[Integer]
g y | [ x | x<-(takeLeThanSqrt y primes), y `mod` x ==0] == [] = [y]
    | otherwise = []

ans::Integer
ans = sum $ takeWhile (<= 2000000) primes

結果，

Prelude> :l e10.hs
[1 of 1] Compiling Main             ( e10.hs, interpreted )
Ok, modules loaded: Main.
*Main> ans
142913828922

けどちょっと時間がかかりすぎてるようで，Haskellだからまだ助かってると思います．

[Perl] イテレータ

Perlで上のイテレータを作ると時間がかかるなんてものではすみません．要検討．サブルーチンの呼び出しがネックと推測．おばかでした．pushを使えばいいのにわざわざリストを展開してました．

#
#Project Euler Problem 10
#iterator version TOO SLOW!!
#
use strict;
use warnings;

use Benchmark;


sub next_cand{
    $_[0] + 2 * ($_[0] % 6 ==5) + 4*($_[0] % 6 ==1);
}

sub primefactory2{
    my @primes=(2,3,5);
    my $state=-1;
    return sub{
        $state++;
        return $primes[$state] if $state==0 or $state==1 or $state==2;
        #my $prime_cand=next_cand($primes[-1]);
        my $prime_cand=next_cand($primes[-1]);
        my $th;
        SIEVE:
         $th = int(sqrt($prime_cand))+1;
        foreach my $d ( @primes ){
            last if $d>$th;
            if ( ($prime_cand % $d ==0)  ){
                $prime_cand = next_cand($prime_cand);
                goto SIEVE; 
            }
        }
        #@primes=(@primes,$prime_cand);#ボトルネック
        push @primes, $prime_cad;
        return $primes[-1];
    }
}

my $x=primefactory2();
my $sum;
my $i;
while (1){
   my $p=$x->();
   last if $p>2000000;
   $sum += $p;
}
print $sum;