「プロジェクトオイラー解説問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で割れるということは１～10それぞれの数の素因数で割ってもaが整数であるということです。


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

1で割るのは自明です。
2で割れるのでaに素因数２が一つ必要なことがわかります。(2)
3で割れるのでaに素因数３が一つ必要なことがわかります。(2,3)
4で割れるのでaには素因数２が２つ必要なことがわかりました。(2,2,3)
5で割れるのでaには素因数5が一つ必要なことがわかります.(2,2,3,5)
6で割れるのですが6の素因数は２と３が一つずつなので(2,2,3,5)のままです。
7で割れるので素因数7が一つ必要なことがわかります(2,2,3,5,7)
8で割れるのでaには２が３つ素因数として必要ですよって(2,2,2,3,5,7)であるとわかります。
9で割れるので3*3で３が二つ必要なことがわかります(2,2,2,3,3,5,7)
10で割れますがこれは２*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のある素因数ｐが増加します。
それは割る数の素因数ｐがすべて同じ数になるときです。
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＾117＾１、19＾１ですから答えは。
2^4*3^2*5*7*11*13*17*19となることがわかります。


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

1でも割り切れるのでA1=1です。
2でも割り切れるのでA2=2
３でも割り切れるので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
,,,
と計算していけば答えが出ます。

----
*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で割れるということは１～10それぞれの数の素因数で割ってもaが整数であるということです。


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

1で割るのは自明です。
2で割れるのでaに素因数２が一つ必要なことがわかります。(2)
3で割れるのでaに素因数３が一つ必要なことがわかります。(2,3)
4で割れるのでaには素因数２が２つ必要なことがわかりました。(2,2,3)
5で割れるのでaには素因数5が一つ必要なことがわかります.(2,2,3,5)
6で割れるのですが6の素因数は２と３が一つずつなので(2,2,3,5)のままです。
7で割れるので素因数7が一つ必要なことがわかります(2,2,3,5,7)
8で割れるのでaには２が３つ素因数として必要ですよって(2,2,2,3,5,7)であるとわかります。
9で割れるので3*3で３が二つ必要なことがわかります(2,2,2,3,3,5,7)
10で割れますがこれは２*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のある素因数ｐが増加します。
それは割る数の素因数ｐがすべて同じ数になるときです。
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＾１、19＾１ですから答えは。
2^4*3^2*5*7*11*13*17*19となることがわかります。


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

1でも割り切れるのでA1=1です。
2でも割り切れるのでA2=2
３でも割り切れるので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
,,,
と計算していけば答えが出ます。