200万までの素数の和

30分プログラム、その269。200万までの素数の和 via Project Euler。
最近、勉強しているErlangでチャレンジ。でも並列計算ではない。
またも失敗。素数は鬼門だ。

• エラトステネスのふるい -> 終了しない。そうかエラトステネスはO(N^2)か
• フェルマーテストでごまかそう -> Erlangの浮動小数の限界を越えた

使い方

1> problem10:solve(2000000).
** exception error: bad argument in an arithmetic expression
     in function  math:pow/2
        called as 
        called as math:pow(146,
                           156)
     in call from problem10:is_fermat/1
     in call from problem10:is_prime/2
     in call from problem10:'-solve/1-lc$^0/1-0-'/1
     in call from problem10:'-solve/1-lc$^0/1-0-'/1
     in call from problem10:solve/1

ソースコード

-module(problem10).
-compile(export_all).

sieve([],L) -> L;
sieve([H|T],L) -> sieve([X || X<-T,X rem H =/= 0],[H|L]).

% solve(N) -> lists:sum(sieve(lists:seq(2,N))).

gcd(M,0)-> M;
gcd(M,N) -> gcd(N,M rem N).
    
is_fermat(2)-> false;
is_fermat(N)->
    A = random:uniform(N-2)+1,
    gcd(A,N) =/= 1 orelse round(math:pow(A,N-1)) rem N =/= 1.

is_prime(_N,0)-> true;
is_prime(N,C) -> 
    case is_fermat(N) of
	true -> false;
	_    -> is_prime(N,C-1)
    end.

is_prime(N) -> is_prime(N,3).

solve(N) -> lists:sum([X || X <- lists:seq(2,N) , is_prime(X)]).

参考

• 過去の30分プログラム
• wikipedia:フェルマーの小定理