Project Euler 問題29（異なるべき乗）を解いてみる

Project Euler で紹介されている問題29を解いてみました。大きな整数を使える言語を利用します。Cの解答例では、他の Unix コマンドと連携して解いています。

Project Euler 問題29（異なるべき乗）

解答例

問題の例で、a^b は16の数字があります。2⁴ = 4² = 16 しか重複する数字がありません。結果として15個の数字の列を得ます。

これを 2 ≦ a ≦ 100、2 ≦ b ≦ 100 の場合に求める問題です。

問題の範囲で、一番大きな数字は 100¹⁰⁰ となります。このため大きな数字を扱えるプログラミング言語を使う必要があります。まず、Pythoh で解いてみます。

最初に a^b（2 ≦ a ≦ 100、2 ≦ b ≦ 100）のリストを作ります。以下のプログラムでは、内包表記を使いました。重複しているリストの要素を取り除くために、集合型 set に変換して、要素数を求めています。

"""Project Euler Problem029"""
p = [i ** j for i in range(2, 101) for j in range(2, 101)]
answer = len(set(p))

print("Problem029: " + str(answer))

やりたいことがすっきりと表現できています。

解答例（他のプログラムと連携する）

C++ には、キーの重複を許可しない連想コンテナ set があります。set を使えば、同じように解くことができます。ただし、多倍長整数のライブラリを使う必要があります。

C は、標準ライブラリでコンテナの機能をほとんど定義していません。重複を許可しない連想コンテナを自作で作ってもよいですが、ここでは、複数のコマンドで作業を分割して問題を解きます。

複数の Unix コマンドで処理を分割することは、問題22でも紹介しました。

最初に a^b の値をすべて求めます。多倍長演算を行うため GMP ライブラリを使います。2 ≦ a ≦ 100、2 ≦ b ≦ 100 に対して、a^b を求めて出力するだけのプログラムにします。

以下は、GMP ライブラリを使った C のプログラムです。

#include <stdio.h>
#include <gmp.h>

int main(void)
{
	int i, j;
	mpz_t n;

	mpz_init(n);

	for (i = 2; i <= 100; ++i) {
		for (j = 2; j <= 100; ++j) {
			mpz_ui_pow_ui(n, i, j);      /* n = i ^ j */
			gmp_printf("%Zd\n", n);      /* print n */
		}
	}

	mpz_clear(n);

	return 0;
}

GMP ライブラリを使うため、演算子ではなく、関数呼び出しで演算を行っています。本質的には、a^b を求めて出力しているだけです（背景色を変更しました）。

このプログラムの出力をソートして（sort）、重複している行を除いて（uniq）、行をカウントする（wc）ことにより解を求めることができます。それぞれのコマンドは、パイプでつないで次のように実行します。なお、C の実行プログラムは、problem029.exe という名前にしています。使った Unix コマンドは、よく使われるものを選んでいます。

./problem029.exe | sort | uniq | wc -l

Python と比較すると、手間がかかっています。言語仕様が貧弱な言語でも、目的とする作業を分割すれば、実現できる例として紹介しました。

最後に

やはり Python は、すっきり書けますね。C でも、他のコマンドと連携すれば、解くことができました。場合によって、Python では、性能が追い付かない場合があるため（例）、性質が異なる言語でプログラムができることは意味があると考えています。

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