「プロジェクトオイラー問１２」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問１２ - (2014/02/13 (木) 02:07:01) のソース

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