Project Euler 49

項差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ。

(i)3つの項はそれぞれ素数である。
(ii)各項は他の項の置換で表される。
1, 2, 3桁の素数にはこのような性質を持った数列は存在しないが、4桁の増加列にはもう1つ存在する。

それではこの数列の3つの項を連結した12桁の数を求めよ。

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2049

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

deque<bool> p;

/*
maxまでの素数を計算する。
あらかじめ 
deque<bool> p; 
をグローバルで宣言しておいてね
*/
void calcPrime(const int max){
	for(int i=0 ; i<max+1 ; i++){
		p.push_back(true);
	}
	p[0] = false;
	p[1] = false;

	double myEnd = sqrt(double(max));
	for(int i=2 ; i < myEnd ; i++){
		for(int j=2 ; i*j<=max ; j++){
			p[i*j] = false;
		}
	}
}

// nが素数かどうか
bool isPrime(int n){
	return p[n];
}


// xを各桁ごとにばらしてdequeに挿入する。
deque<int> integerDigits(long long x){
	deque<int> arr;
	while(x!=0){
		arr.push_front(x%10);
		x/=10;
	}
	return arr;
}


int main(){
	calcPrime(10000);
	deque<int> d1, d2, d3;

	int k;
	for(int i=1000 ; i<10000 ; i++){
		if(!isPrime(i)) continue;

		d1 = integerDigits(i);
		sort(d1.begin(), d1.end());

		for(int j=i+1 ; j<10000 ; j++){
			if(!isPrime(j)) continue;

			d2 = integerDigits(j);
			sort(d2.begin(), d2.end());

			if(!(d1==d2)) continue;

			k = 2*j-i;

			if(k>=10000 || !isPrime(k)) continue;

			d3 = integerDigits(k);
			sort(d3.begin(), d3.end());

			if(d2==d3)
				cout << "i -> " << i << ",j -> " << j << ",k -> " << k << endl;
		}
	}

}

これで1〜50までは全てクリア。