プロジェクトオイラー問33

Problem 33 「桁消去分数」 †

49/98は面白い分数である.「分子と分母からそれぞれ9を取り除くと, 49/98 = 4/8 となり, 簡単な形にすることができる」と経験の浅い数学者が誤って思い込んでしまうかもしれないからである. (方法は正しくないが，49/98の場合にはたまたま正しい約分になってしまう．)

我々は 30/50 = 3/5 のようなタイプは自明な例だとする.

このような分数のうち, 1より小さく分子・分母がともに2桁の数になるような自明でないものは, 4個ある.

その4個の分数の積が約分された形で与えられたとき, 分母の値を答えよ.

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



解法
賢い方法を思いつかなかったので自明な場合を全部排除して、
後は同じ数がある場合を消して試してるだけです。
全然やる気が起きなかった問題なのでコードも適当です。
分数がリスト形式で表示されますので暗算で答えを出してください。

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

check2(X2,X1,Y2,Y1,Ua,Da):-
      U is X2*10+X1,
      D is Y2*10+Y1,
      gcd(U,D,G1),
      U1 is U//G1,
      D1 is D//G1,
      gcd(Ua,Da,G2),
      U1=:=Ua//G2,
      D1=:=Da//G2,
      write([U1,'/',D1]),
      fail.


check(X2,X1,Y2,Y1):-
      X2*10+X1>=Y2*10+Y1,
      !,
      fail.
check(_,0,_,0):-!,fail.
check(X,X,Y,Y):-!,fail.

check(X2,X1,X2,Y1):-
      !,
      check2(X2,X1,X2,Y1,X1,Y1).
check(X2,X1,Y2,X2):-
      !,
      check2(X2,X1,Y2,X2,X1,Y2).

check(X2,X1,X1,Y1):-
      !,
      check2(X2,X1,X1,Y1,X2,Y1).
check(X2,X1,Y2,X1):-
      !,
      check2(X2,X1,Y2,X1,X2,Y2).

search:-
      between(1,9,X2),
      between(0,9,X1),
      between(1,9,Y2),
      between(0,9,Y1),
      check(X2,X1,Y2,Y1).
main33:-search.