Project Euler 問題3（最大の素因数）を解いてみる

Project Euler で紹介されている問題3を解いてみました。素因数分解の素朴なプログラミング例と、素因数の性質を使った改善案を紹介します。

問題3（最大の素因数）

解答例

与えられた数（600851475143）を2で割ります（実際には割れませんが）。
　もし2で割れたら最大の素因数（max_prime_factor）としてメモをする。
　さらに2で割り切れるだけ割り切る。

2で割り切れるだけ割った数に対して、次は3で割ります
　以下、同じ操作となります。

これを割り切れるだけ割った数（remain）まで繰り返す。

数が long int で表現できる数よりも大きいため、unsigned long long int を使います。型名が長いため、typedef することにします。

これを素直に実装しました。実装言語は C です。

#include <stdio.h>

typedef unsigned long long int ull;
#define TARGET_NO 600851475143

int main(void)
{
	ull i;
	ull target = TARGET_NO;
	ull remain = target;
	ull max_prime_factor = 1;

	for (i = 2; i <= remain; ++i) {
		if (remain % i == 0) {
			max_prime_factor = i;
			remain = remain / i;
			while (remain % i == 0) {
				remain = remain / i;
			}
		}
	}

	printf("Problem003: %lld\n", max_prime_factor);

	return 0;
}

小さい数から割れるだけ割っていきますので、結果的に割れる数は素数になります。例えば、先に2と3で割れるだけ割っているため、remain は素因数として2と3を含まず、当然6（= 2 × 3）では割れません。

考察

調べる数が固定されていては、アルゴリズムの性質がわかりにくいため、任意の数の素因数分解を行うプログラムに作り替えてみましょう。

#include <stdio.h>

typedef unsigned long long int ull;

int main(void)
{
	ull i;
	ull target;
	ull remain;

	scanf("%lld", &target);
	printf("%lld:", target);
	remain = target;

	for (i = 2; i <= remain; ++i) {
		while (remain % i == 0) {
			printf(" %lld", i);
			remain = remain / i;
		}
	}

	printf("\n");

	return 0;
}

プログラムを動かすと入力待ちになります。整数を1つ入力すると、素因数をすべて出力して、プログラムを終了します。試しに問題にある
　　600851475143
を入力すると、すべての素因数を出力します。次に
　　600851475149
を入力してください。はい、戻ってきませんね（paiza.IO で試したら、Timeout しました）。これは、600851475149 が素数なので、大きな数まで割っていく必要があり、計算機はがんばっているのですが、計算が終了しなくなっています。合成数の場合でも
　　600851475145　（= 5 × 120170295029）
は計算量が多く戻ってきません。これは片方の素因数が大きいためです。

工夫してみましょう。

$n$ が自然数の積 $a \times b$ と書けるなら、$a$ か $b$ のどちらかは、$\sqrt{n}$ 以下となります。ですから、割る数は、$\sqrt{n}$ まで調べればよいわけです。$\sqrt{n}$ までの数で割り切って残った数は素数となることも分かります。

素因数分解プログラムの改善版

この原理を用いた実装は以下です（$\sqrt{n}$ を求める代わりにループカウンタを二乗しています）。

#include <stdio.h>

typedef unsigned long long int ull;

int main(void)
{
	ull i;
	ull target;
	ull remain;

	scanf("%lld", &target);
	printf("%lld:", target);
	remain = target;

	for (i = 2; i * i <= remain; ++i) {
		while (remain % i == 0) {
			printf(" %lld", i);
			remain = remain / i;
		}
	}

	if (remain != 1) {
		printf(" %lld", remain);
	}
	printf("\n");

	return 0;
}

プログラムとしては、4行（背景色を薄く変更しました）しか変更がありませんが、劇的に速くなっています。このバージョンは、600851475143, 600851475149, 600851475145 に対して待ち時間なく素因数を返してきます。このバージョンは、試した数程度の大きさであれば計算パワーが少ない環境でも動作しますので、気楽に試してみてください。

最後に

$n$ の素因数を求めるためには、$\sqrt{n}$ 以下まで調べればよいことを使って改善しました。簡単な事例ですが、素因数分解の奥深さの一端でも伝わればと思います。

（ユーザは意識しませんが）世界中で使われている暗号アルゴリズムRSAは、大きな素数を2つ掛け合わせた数から元の2つの素数を求めることは、計算量が大きくて難しい、という現象に基づいています。

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