Project Euler 47

連続する2つの数がそれぞれ2つの異なる素因数を持つのは

14 = 2 × 7
15 = 3 × 5 の場合である.
同様に連続する3つの数がそれぞれ3つの異なる素因数を持つのは

644 = 22 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19 の場合である.
連続する4つの数がそれぞれ4つの異なる素因数を持つ場合を考え, 連続する数の中で最小のものを答えよ.

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

#include <iostream>
#include <deque>

using namespace std;

//素数を max まで計算する
deque<bool> p;
deque<int> prime;
void calc_prime(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;
		}
	}
	for(int i=2 ; i<=max ; i++){
		if(p[i]) prime.push_back(i);
	}
}

// nの素因数分解し、異なる素数の個数を返す。
// 4 = 2*2 なので　ret=1
// 12 = 2*2*3 なので ret=2
// 30 = 2*3*5 なので ret=3
int factDistinctNum(int n){
	int ret=0;
	int i=-1, k;

	bool t;
	while(n!=1){
		i++;
		t=true;
		k=prime[i];

		while(n%k==0){
			n /= k;
			if(t){
				ret++;
				t=false;
			}
		}
	}
	return ret;
}

int main(){
	calc_prime(1000000);

	for(int i=1 ; i<1000000 ; i++){

		if(factDistinctNum(i)!=4) continue;
		if(factDistinctNum(i+1)!=4){
			i+=1;
			continue;
		}
		if(factDistinctNum(i+2)!=4){
			i+=2;
			continue;
		}
		if(factDistinctNum(i+3)!=4){
			i+=3;
			continue;
		}

		cout << i << " " << i+1  << " " << i+2 << " " << i+3 << endl;
		break;
	}
}

計算時間がクソ。因数分解の部分をほんとはもう少し考えないといけないが・・・