Project Euler 問題12（多くの約数を持つ三角数）を解いてみる

Project Euler で紹介されている問題12を解いてみました。約数の個数を求める関数を改善していきます。

問題12（多くの約数を持つ三角数）

　 1: 1
　 3: 1,3
　 6: 1,2,3,6
　10: 1,2,5,10
　15: 1,3,5,15
　21: 1,3,7,21
　28: 1,2,4,7,14,28

解答例

約数の個数求める関数 n_of_divisors を素直に実装してみましょう。

約数の個数を求めたい数 number を、1 から number までの数で割っていき、割り切れれば（余りが0であれば）、約数としてカウントしていきます。C の実装です。

#include <stdio.h>

int n_of_divisors(int number)
{
	int answer = 0;
	int i;

	for (i = 1; i <= number; ++i) {
		if ((number % i) == 0) {
			++answer;
		}
	}

	return answer;
}

int main(void)
{
	int i, triangle_no, divisors;

	i = 1;
	triangle_no = 1;
	divisors = 1;

	while ((divisors <= 500)) {
		++i;
		triangle_no += i;
		divisors = n_of_divisors(triangle_no);
	}

	printf("Problem012: %d\n", triangle_no);
	printf("Problem012: %dth triangle number has %d divisors\n", i, divisors);

	return 0;
}

このプログラムは、約数の個数を分かりやすく求めていますが、効率は悪く、わたしの環境（Windows cygwin 上の user time）で、9分以上の時間がかかりました。

解答例（改善版1）

関数 n_of_divisors を少し改善してみましょう。元のプログラムは、1 から調べる数まですべての数で割っていましたが、調べる数そのものを除く最大の約数は、あっても元の調べる数を2で割ったものなので、ループの回数を半分にできます。

また、1と調べる数は、必ず約数になるので、計算する必要はありません。このアイデアで実装した n_of_divisors は次のようになります（関数だけ示します）。

int n_of_divisors(int number)
{
	int answer;
	int i;

	answer = 2; /* 1 and number */
	for (i = 2; i <= (number / 2); ++i) {
		if ((number % i) == 0) {
			++answer;
		}
	}

	return answer;
}

関数のループが半分になりましたが、それでもこのプログラムは4分以上の時間がかかりました。また。このバージョンの n_of_divisors は、1に対して約数の個数を2個と返します。2以上の数に対しては、正しい約数の個数が返せますが、気になる制約です。

解答例（改善版2）

問題3の考察で紹介しましたが、$n$ が自然数の積 $a \times b$ と書けるなら、$a$ か $b$ のどちらかは、$\sqrt{n}$ 以下となります。ですから、割る数は、$\sqrt{n}$ まで調べればよいわけです。割り切れれば2個の約数が見つかります。注意としては、平方数の場合で、例えば25の約数は、以下の3個となります。

　25: 1, 5, 25

平方数の場合は、その平方根は約数になりますが、これは1個のみ現れます。このアイデアで実装した n_of_divisors と問題を解くプログラムは以下になります。

#include <stdio.h>

int n_of_divisors(int number)
{
	int answer = 0;
	int i;

	for (i = 1; i * i <= number; ++i) {
		if ((number % i) == 0) {
			if (i * i != number) {
				answer += 2;
			} else {
				++answer;
			}
		}
	}

	return answer;
}

int main(void)
{
	int i, triangle_no, divisors;

	i = 1;
	triangle_no = 1;
	divisors = 1;

	while ((divisors <= 500)) {
		++i;
		triangle_no += i;
		divisors = n_of_divisors(triangle_no);
	}

	printf("Problem012: %d\n", triangle_no);
	printf("Problem012: %dth triangle number has %d divisors\n", i, divisors);

	return 0;
}

この改善版は、コマンド実行と同時に答えが出力されており、十分な速さになりました。

測定結果

以下は、私の個人PC（プロセッサ：Intel Core i7-10700 @2.90GHz、メモリ 32GB）での測定結果です。キャッシュや他のプログラムの影響もあるため、毎回同じとはなりませんが、速度の目安になるかと思います。測定環境は、cygwin コンソールの time コマンドで測定した user time です。なお、user time が大きい場合、測定誤差の絶対値も大きくなるため、2回の測定時間の平均を計算しました。

3通りのプログラムは、関数 n_of_divisors の差しかありません。また、改善版1は、$n/2$ まで調べて、改善版2は、$\sqrt{n}$ まで調べるという差しかありません（ぱっとみた感じでは大きな差があると感じにくいのではないでしょうか）。調べる数字が大きくなっていくと、この差が計算量で考えた場合に、とんでもない大きな差になることが分かります。

最後に

約数の個数を求める関数を改善しました。$n/2$ と $\sqrt{n}$ は、$n$ が大きくなっていくと、大きな差になることがプログラムの実行時間からも確認することができました。

今回のプログラムは、三角数である性質を使っていませんが、三角数であることを活用した改善版があります。数学的な説明が多いため別の記事として、次回に紹介します。