※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。


Problem 5 「最小の倍数」 †

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.


解法
機械的に考えるならlcm(1,2,3,,,,20)ですのでそのまま実装します。

手計算で考えると
1,2,3、、、で割れる数と考えていくと。
1で最初その数は1.
2でその数は2.
3でそのかずは3.
4でその数は2^2で割れるのだから、2が二つ、3が一つ素因数として必要、だから4*3=12.
5でその数は2^2 3 5で割れないとダメだから2^2*3*5.
処で素数pのp^nが20を超えない最大のnがその数に必要な最低限の素因数pの数である。
よってそれを求めて
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).