Project Euler 3

Mathematica C/C++ 
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?
13195の素因数は5,7,13,29です。
600851475143の最大の素因数はいくつでしょう。

Mathematica

これはMathematicaでやる場合は非常に簡単にできます。

Max[FactorInteger[600851475143]]

FactorInteger*1を使うのは卑怯かな・・・

C/C++

さて、C++。案の定苦労した！
まず、問題で出されている数 600851475143 は long には収まりません。unsigned long long intとかだったらできるかもしれませんが、project eulerでは100桁以上の数を扱うことも今後頻繁に起こるので、多倍長演算ができるライブラリを探してみました。
最初はGNU Multi-Precision Library(GMP)を導入しようとしましたが、Visual Studioでやってるせいもあるのかよくわからずに断念。
MPIRというものを導入してみました。


VC++ 9.0(Visual Studio 2008)でMPIRを導入する方法(不完全)

1. MPIR公式サイトで、 "MPIR Version 2.0.0 - download source" でtar.gzをダウンロード、解凍。
2. 解凍したフォルダの build.vc9 -> mpir.sln を開く。
3. ビルドする。(このままだと全部コンパイルできてません。なぜかは謎です。[僕が知らないだけ])
4. ビルドが終了したら、2で解凍したmpirフォルダ全体を適当な場所に置く。
5. Visual Studio側で、ツール→オプション→プロジェクト及びソリューション→VC++ディレクトリに移動。
6. 「ディレクトリを表示するプロジェクト」でライブラリファイルを選択、「新しい行」ボタンを押し、4で適当な場所においたmpirフォルダを指定する。
7. 「ディレクトリを表示するプロジェクト」でインクルードファイルを選択、6と同じことをする。

この操作を行った上で、プログラム側で

#pragma comment(lib,"mpir.lib")
#include <mpir.h>

の2行を最初の方に書くことでmpirが使える・・・はず。手順で抜けていることがあったらごめんなさい。
MPIRの中身の仕様については、公式サイトの "Documentation for version 2.0.0" のPDFファイルからどうぞ。


で、長くなりましたが以下が第3問の回答。

#pragma comment(lib,"mpir.lib")
#include <iostream>
#include <vector>
#include <mpir.h>

using namespace std;

vector<unsigned long int> factorize(mpz_t);


int main(){
	mpz_t n;
	vector<unsigned long int> primes;

	mpz_init_set_str(n, "600851475143", 10);

	primes = factorize(n);

	for(int i=0 ; i< (int)primes.size() ; i++){
		cout << primes[i] << endl;
	}

	return 0;
}

/*
n を素因数分解する。
素因数の列をvectorに入れて返すが、素因数の個数は出さないのであとで作りなおさないと・・・
*/
vector<unsigned long int> factorize(mpz_t n){

	vector<unsigned long int> primes;
	mpz_t tmp1;
	unsigned long int a=2;

	mpz_init(tmp1);
	while(1){
		while(1){
			mpz_mod_ui(tmp1, n, a);


			if(mpz_cmp_si(tmp1,0)==0){
				mpz_div_ui(n,n,a);
				primes.push_back(a);
			}
			else break;
		}
		if(mpz_cmp_si(n,1)==0) break;
		a++;
	}
	return primes;

}

mpz_t というのが整数で多倍長演算を行うための型です。
factorize 関数は正直適当に作った。ほんとはvectorの要素を素因数とその個数を入れるための構造体にした方がいいんだろうなぁ。

*1:FactorInteger[n]: 整数nの素因数をこれらの指数とともにリストとして返す。