「プロジェクトオイラー問８７」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー問８７」(2014/03/04 (火) 10:28:12) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

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

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