Problem 87 「3つの素数のべき乗」 †

素数の2乗と素数の3乗と素数の4乗の和で表される最小の数は28である. 50未満のこのような数は丁度4つある.

28 = 2^2 + 2^3 + 2^4
33 = 3^2 + 2^3 + 2^4
49 = 5^2 + 2^3 + 2^4
47 = 2^2 + 3^3 + 2^4

では, 50,000,000未満の数で, 素数の2乗と素数の3乗と素数の4乗の和で表される数は何個あるか?


解法
素数だから特に規則性見出せませんし。
愚直に全探索したくらいです。

not_prime(N):-N<2.
not_prime(N):-
	between(2,N,D),
	(D*D>N -> !,fail;true),
	N mod D=:=0,
	!.

is_prime(N):-!,not(not_prime(N)).

p_list(N):-
	between(2,8000,N),
 	is_prime(N).

search(_,[],Sum,Sum):-!.
search(Ps,[R|Rs],Sum,Result):-
	member(P,Ps),
 	Sum1 is Sum+P^R,
 	(Sum1>5000*10000->!,fail;true),
	search(Ps,Rs,Sum1,Result).


main87:-
	findall(P,p_list(P),Ps),
	findall(E,search(Ps,[2,3,4],0,E),All),
	sort(All,All1),
	length(All1,Ans),
	write(Ans).

タグ:

+ タグ編集
  • タグ:

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

最終更新:2014年03月04日 10:28