プロジェクトオイラー5. ~ Smallest multiple ~

No.5 Smallest multiple

問題.

Q. 2520 は, 1 から 10 のすべてで割り切れる最小の数です.

では, 1 から 20 のすべてで割り切れる最小の数はいくつか.

 

要は 1 から 20 までの数の最小公倍数を求める問題です.

考え方とプログラム例(c++)

1. 1から順に最小公倍数を求めていく

2つの引数 () の最大公約数 を返す関数 を, ユークリッドの互除法を用いて再帰関数で定義します.

2つの数 の最小公倍数 は, 最大公約数を とすると,

\begin{align*}
L = \dfrac{a\times b}{G}
\end{align*}

で求まります.

ちなみに，この問題では特に関係ないのですが，やが大きな数のときに，の計算でオーバーフローしてしまう可能性があるので，最小公倍数を求める場合はがで割り切れることを用いて

\begin{align*}
L = (a / G) \times b
\end{align*}

とすることが多いです．

後は,

\begin{align*}
\mathrm{lcm}(\mathrm{lcm}(\ldots \mathrm{lcm}(\mathrm{lcm}(1, 2), 3), \ldots, 20))
\end{align*}

を求めれば答えになります.

#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
    if(a % b == 0) return b;
    else	return gcd(b, a % b);
}
int main(){
    int ans = 1;
    for(int i = 1; i <= 20; i++)
        ans = i / gcd(ans, i) * ans;
    cout << ans << endl;
    return 0;
}

2. 素数がいくつ答えに含まれるかを考える

今回は20までの最小公倍数ですが，より大きなに対して以下の自然数の最小公倍数を求めようと思うと上の方法では時間がかかってしまいます．そこで，数学的な工夫をして答えを求めていきます.

20以下の素数は, 2, 3, 5, 7, 11, 13, 17, 19 の8個です.

(下のプログラムではエラトステネスの篩によって20以下の素数を求めています. )

すると, 1～20の最小公倍数 は,

\begin{align*}
X = 2^{q_2}\times 3^{q_3}\times\cdots\times17^{q_{17}}\times19^{q_{19}}
\end{align*}

という形になります.

このとき, 20 以下に の倍数が含まれていて, の倍数は含まれていないことになるので,

です. 他の素数 に対する も同様に求められます.

#include<bits/stdc++.h>
using namespace std;
int main(){
    int ans = 1;
    int N = 20;
    int num[N] = {0};
    num[0] = 1;
    int n;
    for(int i = 0; i < N; i++){
        if(num[i] == 0){
            ans *= (pow(i + 1, int(log(N)/log(i+1))));
            n = 2 * (i + 1);
            while(n <= N){
                num[n-1] = 1;
                n += (i + 1);
            }
        }
    }
    cout << ans << endl;
    return 0;
}