Problem 5 「最小の倍数」 †
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.
解法
機械的に考えるならlcm(1,2,3,,,,20)ですのでそのまま実装します。
手計算で考えると
1,2,3、、、で割れる数と考えていくと。
1で最初その数は１．
2でその数は２．
3でそのかずは３．
4でその数は２＾２で割れるのだから、２が二つ、３が一つ素因数として必要、だから4*3＝12.
5でその数は2＾２ ３ 5で割れないとダメだから2＾2*3*5.
処で素数ｐのｐ＾ｎが20を超えない最大のｎがその数に必要な最低限の素因数ｐの数である。
よってそれを求めて
2^4*3^2*5*7*11*13*17*19と求まる。
gcd(0,B,B):-!.
gcd(A,B,Result):-
R is B mod A,
gcd(R,A,Result).
lcm(A,B,Result):-gcd(A,B,G),Result is A*B//G.
calc(21,Ans,Ans):-!.
calc(N,Ans,Result):-
lcm(N,Ans,Ans1),
N1 is N+1,
calc(N1,Ans1,Result).
main5:-calc(1,1,Ans),write(Ans).
最終更新：2014年02月12日 15:38
