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).
最終更新:2014年03月02日 10:22