Problem 10 「素数の和」 †
10以下の素数の和は 2 + 3 + 5 + 7 = 17 である.
200万以下の全ての素数の和を求めよ.
解法
小さい数から試します、N=2は既知として与え、3以上の数Nが素数ならそれを足す処理とします。
素数判定はsqrt(N)までのためし割りでは速度が出ません。
それまで得られた1500以下の数の素数リストで試し割ることで少しだけ速度をあげます。
素数リストを作るときappendを使っています。
appendは効率が悪いという話がありますが、1500以下の素数リスト程度の長さなら気にするほどではないでしょう。
not_prime(N,Primes):-
member(Div,Primes),
(Div*Div>N->!,fail;true),
N mod Div=:=0,
!.
is_prime(N,Primes):-not(not_prime(N,Primes)).
addPrime(N,N,Primes):-is_prime(N,Primes),!.
addPrime(_,0,_):-!.
search(N,Stop,Sum,_,Sum):-
Stop<N,
!.
search(N,Stop,Sum,Primes,Result):-
addPrime(N,Add,Primes),
!,
Sum1 is Sum+Add,
N1 is N+2,
((N<1500,Add>0)->append(Primes,[N],Primes1);Primes1=Primes),
search(N1,Stop,Sum1,Primes1,Result).
main10:-
search(3,200*10000,2,[2],Ans),
write(Ans).
最終更新:2014年02月12日 17:50