Project Euler で紹介されている問題5を解いてみました。今回の問題は、電卓（または電卓アプリ）でも正解を求めることができます。プログラムとしては、方針が異なる2つの解き方を紹介します。
問題5（最小の倍数）
2520は、1から10までのすべての数で割り切れる最小の数である。
1から20までのすべての数で割り切れる最小の正の数を求めよ。
考察
2520と1から10 までの数の関係を考える。
2520 = 2 × 2 × 2 × 3 × 3 × 5 × 7
- 素因数2を3個含むため、2、4、8で割り切れる。
- 素因数3を2個含むため、3、9で割り切れる。
- 素因数5を1個含むため、5で割り切れる。
- 素因数7を1個含むため、7で割り切れる。
- 素因数2と3を含むため、6で割り切れる。
- 素因数2と5を含むため、10で割り切れる。
1から20までも同じ考え方で答えを求めることができる。
- 2 × 2 × 2 × 2 を素因数に含むと、2、4、8、16で割り切れる。
- 3 × 3 を素因数に含むと、3、9で割り切れる。
- 5、7、11、13、17、19を素因数に含むと、それぞれの素因数で割り切れる。
- 上記の素因数を含むと、以下の合成数でも割り切れる。
6（2×3）、10（2×5）、12（2×2×3）、14（2×7）、
15（3×5）、18（2×3×3）、20（2×2×5）
つまり、以下の数は、1から20までのすべての数で割り切れる。
2 × 2 × 2 × 2 × 3 × 3 × 5 × 7 × 11 × 13 × 17 × 19
また、この数から素因数をひとつでも抜くと、割り切れない数がでてくる。例えば、素因数2をひとつ抜くと16で割り切れなくなり、素因数3をひとつ抜くと9で割り切れなくなる。つまり、この数は、条件を満たす最小の数となる。
この数は、一般的な電卓でも計算できます。得られた数は2520と比較すると大きな数になると感じる人が多いのではないでしょうか。
プログラムでの解答例
プログラムで解くことも考えてみましょう。
すでに考えた考察をコードとして表現します。
2から20までの素数に対して、20を超えない範囲でその素数の最大の累乗を求めて、それを掛け合わせていけば、題意の数が得られます。
下請け関数を2つ用意します。
- 関数 is_prime
引数 n として自然数を与えて、n が素数なら1を返して、合成数なら0を返す。
注意としては、1は素数ではないため0を返します。 - 関数 prime_power
引数 p と n を与えて、n を超えない範囲で p の最大の累乗を返す。
計算する値は（感覚より）大きくなるため、解答を保存しておく変数（answer）は、unsigned long long int で行うことにしました。以下は、C で実装です。
#include <stdio.h>
typedef unsigned long long ull;
int is_prime(int n)
{
int answer = 1;
int i;
if (n == 1) {
answer = 0; /* 1 is not a prime number. */
}
for (i = 2; i * i <= n; ++i) {
if (n % i == 0) {
answer = 0;
break;
}
}
return answer;
}
ull prime_power(ull p, ull n)
{
ull answer = 1;
while ((answer * p)<= n) {
answer *= p;
}
return answer;
}
int main(void)
{
ull answer = 1;
int i;
for (i = 2; i <= 20; ++i) {
if (is_prime(i) == 1) {
answer *= prime_power(i, 20);
}
}
printf("Problem005: %lld\n", answer);
return 0;
}下請け関数を2つ用意したため、main 関数の実装は、読みやすくなりました。
プログラムでの解答例（別解）
別の考え方も示します（改善版というわけではありません）。
2から20までの数（i）と、求める解答の数（answer）との最大公約数を求めて、その最大公約数が i より小さい場合は、i が求める解答の数に含まれない素因数を含んでいることになります。その素因数を求めて、これを掛け合わせていけば、求める数が得られます。
この別解は、以下の下請け関数を使います。
- 関数 gcd
引数 a と b を与えて、a と b の最大公約数（GCD: Greatest Common Divisor）を返します。アルゴリズムは、ユークリッドの互除法を使うため、高速に動作します。
#include <stdio.h>
typedef unsigned long long ull;
ull gcd(ull a, ull b)
{
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
int main(void)
{
ull i;
ull temp;
ull answer = 1;
for (i = 2; i <= 20; ++i) {
temp = gcd(answer, i);
if (temp < i) {
answer *= i / temp;
}
}
printf("Problem005: %lld\n", answer);
return 0;
}ユークリッドの互除法で最大公約数を求めることは、高校数学（数学A「整数の性質」）で履修します。
最後に
電卓でも解答を導くことができる範囲の問題でしたが、プログラムでの手順を考えるのは楽しく、2例を示しました。ここで紹介した is_prime と gcd は、整数に関係する問題を解くときに、よく使われる関数となります。
引き続き、Project Euler の問題を紹介していきます。
