Project Euler 問題41（パンデジタル素数）を解いてみる

Project Euler で紹介されている問題41を解いてみました。パンデジタルな最大の素数を求めます。ライブラリで順列を使える C++ を利用して解きました。

Project Euler 問題41（パンデジタル素数）

考察

パンデジタル数については、問題32、問題38でも取り扱いました。パンデジタル数は、0 を含む場合もあるようです。Wikipedeia の「パンデジタル数」の定義では、0 を含めています。この問題では、Project Euler の流儀に従います。

3桁のパンデジタル数は、各桁の数を加えると 1 + 2 + 3 = 6 となります。各桁の和が3で割れる数は、3の倍数となるため、素数にはなりません。他の場合も確認してみます。

• 2桁の場合、1 + 2 = 3 となるため、3の倍数となる。
• 3桁の場合、1 + 2 + 3 = 6 となるため、3の倍数となる。
• 5桁の場合、1 + 2 + … + 5 = 15 となるため、3の倍数となる。
• 6桁の場合、1 + 2 + … + 6 = 21 となるため、3の倍数となる。
• 8桁の場合、1 + 2 + … + 8 = 36 となるため、3の倍数となる。
• 9桁の場合、1 + 2 + … + 9 = 45 となるため、3の倍数となる。

パンデジタルな数が素数になるためには、4桁か7桁であることが必要なことが分かりました。7桁の場合を調べれば、最大のパンデジタル素数を求めることができそうです。

解答例

C では標準ライブラリで順列のサポートがありません。標準ライブラリで順列のサポートがあるC++を使って解きます。

最大値を求めるため、ひとつ前の順列を生成する prev_permutataion を使います（38行目）。考察で確認したように 7 桁の場合を計算します。

素数であるか判定する is_Prime は、道具箱から流用しました。

以下は、C++ のプログラムです。

#include <iostream>
#include <algorithm>

using namespace std;

int is_prime(int n)
{
	int answer = 1;
	int i;

	if (n <= 1) {
		answer = 0;
	}
	for (i = 2; i * i <= n; ++i) {
		if (n % i == 0) {
			answer = 0;
			break;
		}
	}

	return answer;
}

int main(void)
{
	int n[7] = {7, 6, 5, 4, 3, 2, 1};

	int answer = -1;
	do {
		int num = 0;
		for (int i = 0; i < 7; ++i) {
			num = num * 10 + n[i];
		}
		if (is_prime(num)) {
			answer = num;
			break;
		}
	} while (prev_permutation(n, n + 7));

	printf("Problem041: %d\n", answer);

	return 0;
}

7桁のパンデジタル素数が見つかり、このプログラムの出力が正解と判定されました。

最後に

パンデジタル素数は、4桁か7桁になるため、7桁の場合を調べて正解を求めることができました。

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