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

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2014年03月02日 10:22