プロジェクトオイラー問１２ - c21coterie @ ウィキ

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個以上の約数をもつ最初の三角数はいくつか.

解法
三角数はD=n(n+1)/2で、約数の個数はDを小さいほうからsqrt(D)までためし割りして素因数の数を求めても答えが出ますが。
ｎとｎ+1それぞれをためし割りで素因数を求め、その組み合わせ数を掛け算したほうが速くなるはずです。
そのように実装しました。

mod2Dell(2,0,1):-!.
mod2Dell(2,1,1):-!.
mod2Dell(2,Count,Count1):-!,Count1 is Count-1.
mod2Dell(_,Count,Count).

div(P,N,N,Count,Count1):-N mod P>0,!,mod2Dell(P,Count,Count1).
div(P,N,ResultN,Count,Result):-
	!,
	N1 is N//P,
	Count1 is Count+1,
	div(P,N1,ResultN,Count1,Result).

calc(1,_,Mult,Mult):-!.
calc(N,P,Mult,Result):-
	P2 is P^2,
	N<P2,
	!,
	mod2Dell(P,2,NowMult),
	Result is Mult*NowMult.

calc(N,P,Mult,Result):-
	!,
 	div(P,N,N1,1,NowMult),
	P1 is P+1,
	Mult1 is Mult*NowMult,
	calc(N1,P1,Mult1,Result).

search(N,Result):-
	N1 is N+1,
 	calc(N, 2,1,Perm1),
	calc(N1,2,1,Perm2),
	Perm3 is Perm1*Perm2,
        500=<Perm3,
	Result is (N*(N+1))/2,
	!.
search(N,Result):-
	N1 is N+1,
	search(N1,Result).
main12:-search(1,Ans),write(Ans).