プロジェクトオイラー問9 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%209
Problem 9 「特別なピタゴラス数」 †
ピタゴラス数(ピタゴラスの定理を満たす自然数)とは a < b < c で以下の式を満たす数の組である.

a^2 + b^2 = c^2
例えば, 3^2 + 4^2 = 9 + 16 = 25 = 5^2 である.

a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する.
これらの積 abc を計算しなさい.

原始ピタゴラス数を求める公式の周長が1000を割り切ればそれをｋ倍すれば答えです。

gcd(0, B, G) :- G is abs(B).
gcd(A, B, G) :- A =\= 0, R is B mod A, gcd(R, A, G).


main:-
	between(2,40,M),
	between(1,M,N),
	(M-N) mod 2=:=1,
	gcd(M,N,G),
	G=:=1,
	L is 2*M*(M+N),
	1000 mod L=:=0,
	K is 1000//L,
	!,
	Ans is K^3*(M^2-N^2)*(2*M*N)*(M^2+N^2),
	write(Ans).

導出木による全探索でも書いてみる。
こっちは原理主義的。

gcd(0,Y,Y):-!.
gcd(X,Y,Z):-
	Y1 is Y mod X,
	gcd(Y1,X,Z).
 
b(K,M):-
	M2 is M*(M+1),
	K<M2,
	!,
	fail.
b(K,M):-
	0 is K mod M,
	N is K//M-M,
	N>0,
	M>N,
	1 is (M-N) mod 2,
	gcd(M,N,Z),
	Z is 1,
	K3 is (500//K)^3,
	Ans is K3*(M*M-N*N)*2*M*N*(M*M+N*N),
	write([ans,Ans]).
b(K,M):-
	M1 is M+1,
	b(K,M1).
 
 
a(K):-
	K2 is K*K,
	500<K2,
	!,
	fail.
a(K):-
	0 is 500 mod K,
	K1 is 500//K,
	b(K1,2).
a(K):-
	0 is 500 mod K,
	b(K,2).
a(K):-
	K1 is K+1,
	a(K1).
 
main:-a(1).