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

Problem 12 「高度整除三角数」 †

三角数の数列は自然数の和で表わされ, 7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である. 三角数の最初の10項は:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

となる.

最初の7項について, その約数を列挙すると, 以下のとおり.

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

これから, 7番目の三角数である28は, 6個以上の約数をもつ最初の三角数であることが分かる.

では, 500個以上の約数をもつ最初の三角数はいくつか.

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

解法

Ｐｒｏｌｏｇ言語

ｎ*(ｎ+1)/2はｎとｎ+1は互いに素で共通素因数を持ちません。

なのでｎとｎ+1を個別に素因数を求めて掛け算すると少し計算が速くなります。

divs(N,2,C,N,C1):-N mod 2>0,!,C1 is C-1.
divs(N,D,C,N,C):-N mod D>0,!.
divs(N,D,C,ReN,ReC):-
      !,
      N1 is N // D,
      C1 is C+1,
      divs(N1,D,C1,ReN,ReC).

yakusu_count(1,_,Count,Count):-
      !.
yakusu_count(N,D,Count,Count1):-
      N<D*D,
      !,
      divs(N,N,1,_,Mult),
      Count1 is Count*Mult.
yakusu_count(N,D,Count,Result):-
      N mod D=:=0,
      !,
      divs(N,D,1,N1,Mult),
      Count1 is Count*Mult,
      D1 is D+1,
      yakusu_count(N1,D1,Count1,Result).
yakusu_count(N,D,Count,Result):-
      !,
      D1 is D+1,
      yakusu_count(N,D1,Count,Result).
yakusu_count_w(N,Result):-
      !,
      yakusu_count(N,2,1,Result).

search(N):-
      N1 is N+1,
      yakusu_count_w(N,M),
      yakusu_count_w(N1,M1),
      500=<M*M1,
      !,
      Ans is (N*N1)//2,
      write(Ans).
search(N):-
      !,
      N1 is N+1,

      search(N1).