「プロジェクトオイラー問７７」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問７７ - (2014/03/02 (日) 10:22:37) のソース

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2077

*Problem 77 「素数の和」 †
10は素数の和として5通りに表すことができる:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

素数の和としての表し方が5000通り以上になる最初の数を求めよ.

解法
5000通りと少ないので全探索しても十分間に合います。


 not_prime(N):-N<2,!.
 not_prime(N):-
 	between(2,N,R),
 	(R*R>N -> !,fail;true),
 	N mod R=:=0,
 	!.
 
 is_prime(N):-not(not_prime(N)).
 
 search2(0,_,1):-!.
 search2(N,Down,Result):-
  	between(Down,N,D),
 	is_prime(D),
 	N1 is N-D,
 	search2(N1,D,Result).
 
 search1(N):-
 	findall(C,search2(N,2,C),Count),
  	length(Count,Ans),
 	Ans1 is Ans-1,
 	5000=<Ans1,
 	!,
 	write(N).
 
 search1(N):-
 	N1 is N+1,
 	search1(N1).
 
 main77:-
 	search1(4).