Project Euler 問題1（3と5の倍数）を解いてみる

Project Euler で紹介されている最初の問題を解いてみました。記念すべき最初の問題です。素直なプログラムでも解けますが、ひと工夫する余地もあるため、その工夫も含めて紹介します。

問題1（3と5の倍数）

解答例

整数（自然数）のデータ、繰り返し、条件判断、出力ができれば、どのプログラミング言語でも解くことができるでしょう。C での記述例です。

#include <stdio.h>

int main(void)
{
	int i;
	int sum = 0;

	for (i = 1; i < 1000; ++i) {
		if ((i % 3 == 0)||(i % 5 == 0)) {
			sum += i;
		}
	}

	printf("Problem001: %d\n", sum);

	return 0;
}

C は、多くのプログラミング言語に影響を与えています。繰り返し文（for）や条件文（if）は、他のプログラミング言語が分かる人であれば、読める人が多いのではないでしょうか。 if 文の条件式が、この問題を解く本質的な記述となっており、”%” が余りを求める演算子で、(i % 3 == 0) は、「i を 3 で割った余りが 0 になる」という意味になります。”||” は論理ORの演算子です。

考察

上記のプログラム例でも、十分に速く解くことができますが、改善の余地があります。問題では、1から1000まで繰り返していますが、この上限が100万になると、1000倍の繰り返しが発生します。この問題は、上限が大きな数になっても、以下の考え方を使えば、それほど計算する量が増えない方法で答えを求めることができます。

求める3の倍数の和は、
　　$3 + 6 + \dots + 999$
となります。一方、5の倍数の和は、
　　$5 + 10 + \dots + 995$
となります。これをどちらも足すと、3と5の最小公倍数である15の倍数は2回足されるため、15の倍数の和
　　$15 + 30 + \dots + 990$
を引いておく必要があります。まとめると、この問題の答えは、
　　（3の倍数の和）+（5の倍数の和）－（15の倍数の和）
となります。

高校数学（数学B「数列」）で履修する範囲ですが、1 から n の和は
　　$ n \times (n + 1) / 2$
と計算できます。1から1000までの3の倍数の和は、$1000 / 3 ＝ 333$ 余り $1$ であるため
　　$3 + 6 + \dots + 999$
　　$= 3 \times (1 + 2 + \dots + 333)$
　　$= 3 \times 333 \times (333 + 1) / 2$
となります。5の倍数についても、15の倍数についても同様の方法で求めることができます。この計算を用いた改善版が以下です。

解答例（改善版）

#include <stdio.h>

int sum_divisible_by(int n, int end)
{
	int p;

	p = end / n;

	return n * p * (p + 1) / 2;
}

int main(void)
{
	int sum;

	sum = sum_divisible_by(3, 999) + sum_divisible_by(5, 999)
	    - sum_divisible_by(15, 999);

	printf("Problem001: %d\n", sum);

	return 0;
}

関数 sum_divisible_by は、1から end までの n の倍数を返す関数です。注意としては、問題は「1000未満」ですので、end には、999 を指定する必要があります。
プログラムの行数は増えていますが、計算量は、かなり小さくなっています。
関数 sum_divisible_by の名前は、Project Euler が正解者向けに公開している解説を参考にしました。

最後に

Project Euler としては、最初の問題でもあり、解きやすい問題だったのではないでしょうか。Project Euler が公開しているデータによると、2022年8月の時点で、100万人近い人がこの問題に正解していました。

なお、見た目が近い問題に Fizz Buzz がありますが、Fizz Buzz の方が、ほんの少しですが難しいかもしれません（条件文が複数ある書き方が素直な実装ですが、判断する順序に注意が必要）。

引き続き、Project Euler の問題を紹介していきます。