3 または 5 で割り切れる数の合計

少し前にその存在を知ったものの, いままで特に気にかけていなかったウェブサイトがあります. Project Euler です. おそらく id:fumokmm さんの「1000以下の回文素数で最大のものを示せ」をGroovyでやってみた (Jul 3, 2011) という記事で見かけたのが, そのサイトの存在を知るきっかけだったと記憶しています.

最近, プログラミングの基礎的なところに再入門し, C 言語やアルゴリズムを学んでいるところでしたので, ふと Project Euler のことを思い出しました.

Project Euler には, おもに算数や数学の簡単な問題がいろいろ掲載されています. おそらく初級的なプログラミングの練習にはうってつけなのではないかと思います. そこで, わたしも少しチャレンジしてみることにしました.

記念すべき第 1 問目, Problem 1 (Oct 5, 2001) には, 次のような問題が出題されています.

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

つまり, 1000 未満の自然数のうち 3 または 5 で割り切れる数をすべて足し合わせて, その合計を答えなさい, ということだと思います.

最もシンプルな解き方

おそらく誰もが最初に思いつき, そして最もシンプルだろうと思われる解き方は, 1 から 999 までの各整数につき, 3 または 5 で割り切れるかどうかを調べ, 割り切れるのであればそれを合計に足して行く, というものだと思います. たとえば, 次のようなものになりましょうか.

int sum0(int x, int y, int sup) {
  int sum, i;
  sum = 0;
  for (i = 1; i <= sup - 1; i++)
    if (i % x == 0 || i % y == 0)
      sum += i;
  return sum;
}

前掲の問題を解くにあたっては, 引数 x に 3 を, 引数 y に 5 を, 引数 sup に 1000 を, それぞれ渡すことになります.

引数 sup は, 英語の supremeum の略です. 「何々未満」というものを表現したかったので, 最大値を意味する maximum はちょっと違うと思いました. その代わり, 上限 (もしくは「上界における最小値」 ?) を意味する supremum であれば, たぶん当たらずといえど遠からずなのではないか, そんなふうに思うのです.

さて, これだけでは, さすがにちょっと物足りない気がします. 雰囲気的には FizzBuzz 問題に少しは似ているのでしょうか. (そういえば, 最近 Twitter 上でも FizzBuzz 問題が少し話題になっていましたね.) 単に愚直に 1 から 999 まで for ループを回すのもいいのですが, それ以外にも何か解き方はないものでしょうか.

掛け算をしてみる解き方

二つの自然数 x または y で割り切れる数というものは, たとえば k x^m yⁿ と表現することができるのではないかと思います. ただし, k, m, n はいずれも整数とし, 1≤k, 0≤m, 0≤n, 1≤m+n とします. ここで, k と m と n を使った 3 重の for ループを回すことにすれば, x または y で割り切れる数が次々に得られるのではないでしょうか.

ただし, k が x または y で割り切れる数の場合は重複することにもなってしまいますので, その場合はスキップするようにする必要があります. そのうえで, 次のようなコードを考えてみました.

#include <math.h>

int sum1(int x, int y, int sup) {
  int sum, k, m, n, tmp;
  sum = 0;
  for (k = 1; k <= (sup - 1) / x || k <= (sup - 1) / y; k++) {
    if (k % x == 0 || k % y == 0)
      continue;
    for (m = 0; m <= (int)(log(sup - 1) / log(x)); m++)
      for (n = 0; n <= (int)(log(sup - 1) / log(y)); n++)
        if (0 < m + n) {
          tmp = k * round(pow(x, m)) * round(pow(y, n));
          if (sup <= tmp)
            break;
          sum += tmp;
        }
  }
  return sum;
}

しかしながら, 実際にいろいろ計測してみたところ, 繰り返しの回数は先ほどのシンプルな解き方よりもむしろ多くなってしまいました. それだけでなく, pow 関数を使っている付近で型変換や丸め誤差の調整っぽいことなどを繰り返したり, そもそも掛け算を多用したりしているからでしょうか, 処理にかかる時間もえらく長くなってしまいました. ざっくり言うと, およそ 100 倍の時間がかかってしまいました. おもしろい解き方かなあと期待していたのですが, ちょっと使い物にはならなかったようです.

和集合で考えてみる解き方

発想を変えます。 x で割り切れる数の個数 a とし, y で割り切れる数の個数を b とし, x および y で割り切れる数の個数を c とすると, x または y で割り切れる数の個数は a + b - c となるはずです. これを利用してみます.

int sum2(int x, int y, int sup) {
  int sum, i;
  sum = 0;
  for (i = 1; i <= (sup - 1) / x; i++)
    sum += i * x;
  for (i = 1; i <= (sup - 1) / y; i++)
    sum += i * y;
  for (i = 1; i <= (sup - 1) / (x * y); i++)
    sum -= i * (x * y);
  return sum;
}

まず, x の倍数を足し上げ, 次に y の倍数を足し上げます. すると, x および y の倍数 (つまり xy の倍数) はダブルカウントしていることになるので, 最後に x および y の倍数 (つまり xy の倍数) を引いて行きます.

この解き方ですと, 最初のシンプルな解き方に比べて, 繰り返し処理の回数は半分以下で済みますし, 繰り返し処理の中で x で割り切れるだろうか, または y で割り切れるだろうか, などと条件判定する必要がないからでしょうか, 実際の処理にかかる時間は 3 分の 1 くらいになりました.

まとめ

本件の問題においては, 引数 x に 3 を, 引数 y に 5 を, そして引数 sup に 1000 を渡してあげることで, sum0, sum1, sum2 のいずれの関数も 233168 という答えを返しました. また, 3 とおりの解き方のうちでは, 第 3 の解き方, すなわち sum2 関数が最も速く処理を終えました. 個人的には, 単に愚直に 1 から 999 まで for ループを回すのとは別の, 少しは効率的な解き方を見つけることができた気分で, とりあえず勉強になった気がします.