「プロジェクトオイラー解説問5」の編集履歴(バックアップ)一覧に戻る

プロジェクトオイラー解説問5 - (2014/01/09 (木) 16:15:56) のソース

----
*Problem 5 「最小の倍数」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%205
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

----
解法
この問題は手計算で解けます。
1~10の場合を分析してみましょう。
答えをaと考えます。
aの素因数をp1,p2,p3,,pnとします。
a=p1^a1*p2^a2*,,pn^an
です。
1~10で割れるということは1~10それぞれの数の素因数で割ってもaが整数であるということです。


aの素因数を()で書いてみます。
aはどんな条件を満たしてる数か1~10までの場合で考えてみましょう。

1で割るのは自明です。
2で割れるのでaに素因数2が一つ必要なことがわかります。(2)
3で割れるのでaに素因数3が一つ必要なことがわかります。(2,3)
4で割れるのでaには素因数2が2つ必要なことがわかりました。(2,2,3)
5で割れるのでaには素因数5が一つ必要なことがわかります.(2,2,3,5)
6で割れるのですが6の素因数は2と3が一つずつなので(2,2,3,5)のままです。
7で割れるので素因数7が一つ必要なことがわかります(2,2,3,5,7)
8で割れるのでaには2が3つ素因数として必要ですよって(2,2,2,3,5,7)であるとわかります。
9で割れるので3*3で3が二つ必要なことがわかります(2,2,2,3,3,5,7)
10で割れますがこれは2*5なので素因数は増えません(2,2,2,3,3,5,7)のままです。
よって答えは
2*2*2*3*3*5*7=8*9*5*7=72*35=2520
であると分かります。
20の場合もこの計算を延長すれば答えが出ます。

もう少し効率的な解法があります。
少し考えてみますとある素因数Pの掛けられる個数が最大になるときaのある素因数pが増加します。
それは割る数の素因数pがすべて同じ数になるときです。
1~20までの素数は2,3,5,7,11,13,17,19ですが。
それぞれの素因数の個数が最大となるのは
2の場合2^4=16
3の場合3^2=9
5の場合5*5は20を超えますので5^1
以下11^1,13^1、17^1、19^1ですから答えは。
2^4*3^2*5*7*11*13*17*19となることがわかります。


コンピュータで計算する場合gcdを使うと効率的に計算できます。
1~nまでで割り切れる数をA1~Anとします。

1でも割り切れるのでA1=1です。
2でも割り切れるのでA2=2
3でも割り切れるのでA3=6です。
4でも割り切れますがgcd(6,4)=2なのでA4=A3*4/2=12です。
5でも割り切れるのでgcd(12,5)=1よりA5=A4*5/1=60
6でも割り切れますがgcd(60,6)=6よりA6=A5*6/6=60
,,,
と計算していけば答えが出ます。