3 個以上の数の最小公倍数

C Project Euler

Project Euler の Problem 5 (Nov 30, 2001) をやってみました.

出題内容は次のとおりです.

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

文中で evenly divisible という言葉には divisible with no remainder という注釈がついています. つまり, 1 から 20 までのいずれの数でも割り切れるもののうち最小のものを答えなさいということですから, 要は 1 から 20 までの整数の最小公倍数を求めることになります.

最大公約数と最小公倍数

あらかじめ, 2 個の整数を与えられたら最大公約数 (GCD) を返す関数と, 最小公倍数 (LCM) を返す関数を, それぞれ作成しておきます.

int gcd(int a, int b) {
  int v0 = a, v1 = b, v2 = a % b;
  while (v2 != 0) {
    v0 = v1;
    v1 = v2;
    v2 = v0 % v1;
  };
  return v1;
}

int lcm(int a, int b) {
  return a * b / gcd(a, b);
}

一応, 最大公約数は, ユークリッドの互除法を用いて求めているつもりです. といっても, いろいろ試行錯誤した結果としてユークリッドの互除法を採用したのではなく, どちらかというとただ単に “馬鹿の一つ覚え” のようなものにすぎません.

最小公倍数の計算を繰り返す方法

今回の問題についてまず思いついたのは, 20 と 19 の最小公倍数を計算し, 次に, 得た数と 18 の最小公倍数を計算し, さらに次に, 得た数と 17 の最小公倍数を計算し, ということを繰り返す方法です.

int get_answer0() {
  int ans = 20, i;
  for (i = 19; 1 < i; --i)
    if (ans % i != 0)
      ans = lcm(ans, i);
  return ans;
}

おそらく最もシンプルな方法かなあと思っています.

最小公倍数の素因数分解された姿をイメージして考えた方法

もうひとつの方法は, 求める数を 2a⋅3b⋅5c⋅7d⋅11e⋅13f⋅17g⋅19h とあらわすことを考え, a, b, ..., h を計算してみる, というものです. 実際には a が 4 で, b が 2 で, あとは 1 だろうということは誰でも気づくところかと思いますが, それだとさすがにつまらないので, 一応この部分は計算してみることにしました.

int power(int a, int b) {
  int p = 1, i;
  for (i = 0; i < b; i++)
    p *= a;
  return p;
}

int get_answer1() {
  int ans = 1;
  int p[] = { 2, 3, 5, 7, 11, 13, 17, 19 };
  int r[8];
  int i, j;
  for (i = 0; i < 8; i++) {
    r[i] = 0;
    j = 1;
    do {
      r[i]++;
      j++;
    } while (power(p[i], j) <= 20);
    ans *= power(p[i], r[i]);
  }
  return ans;
}

C 言語の標準ライブラリ math.h には累乗*1 を計算するための pow 関数がありますが, 浮動小数点数の利用にやや抵抗を感じまして, とりあえず自分で書いてみることにしました.

処理速度の比較

以下のコードで処理速度を比較してみました.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int gcd(int a, int b);
int lcm(int a, int b);
int get_answer0();
int power(int a, int b);
int get_answer1();

int main(void) {
  clock_t t0, t1;
  int i, ans;
  t0 = clock();
  for (i = 0; i < 1000000; i++)
    ans = get_answer0();
  t1 = clock();
  printf("%d %u\n", ans, t1 - t0);
  t0 = clock();
  for (i = 0; i < 1000000; i++)
    ans = get_answer1();
  t1 = clock();
  printf("%d %u\n", ans, t1 - t0);
  return EXIT_SUCCESS;
}

これを実行してみますと, わたしの手元の環境では, たとえば次のようになりました.

232792560 402
232792560 390

いずれの方法も, 答えは 232792560 と出ました. そこそこ大きな数ですね.

さて, 処理速度に関しては, あまり大きな差は見られませんでした. 何度かやってみたところ, 第 1 の方法ではだいたい 400 - 410 ミリ秒, 第 2 の方法ではだいたい 390 - 400 ミリ秒という傾向でした. 個人的には, 第 2 の方法が少しおもしろそうで気に入っておりまして, 掛け算 (特に累乗の計算) が多いからやや時間がかかってしまうかもなあと思っていたのですが, 意外に善戦したような気分です. ただ, 考えてみれば第 1 の方法は掛け算の代わりに割り算が多いので, どっこいどっこいで, こんなものなのかもしれません.

*1:ふだん累乗といってみたり冪乗といってみたりしていますが本当はどちらが正しいでしょう.