※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。


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).