プロジェクトオイラー問47 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2047
Problem 47 「異なる素因数」 †
4つの異なる素因数からなる４つの連続した数のうち最初の数を答えよ。

適当に上限を定めてあとは素因数から数を生成し４つの素因数を持つものだけを記録。
生成できた数を小さいほうから連続でチェックし、４連続のところを探すだけです。
計算時間は0.047sec。

#include<stdio.h>
#include<vector>
#include<set>

const int LIMIT=500000;
bool not_prime[LIMIT]={1,1,0};
std::vector<int> primes;
std::set<int> memo;

void saiki(int point,int count,__int64 num){
	if(num>=LIMIT)return ;
	if(count==4)memo.insert((int)num);
	saiki(point,count+(num==1),num*primes[point]);
	if(count>3)return ;
	for(int point2=point+1;point2<primes.size();point2++){
 		__int64 num2 = num*primes[point2];
		if(num2>=LIMIT)break;
		saiki(point2,count+1,num2);
	}
	
}


int main(){
	for(int i=2;i*i<LIMIT;i+=1+(i&1)){
		if(not_prime[i]==true)continue;
		int start=4,add=2;
		
		if(i%2==1){
			start=i*3;
			add=i*2;
		}
	for(int j=start;j<LIMIT;j+=add){
			not_prime[j]=true;
		}
	}
	primes.push_back(2);
	for(int i=3;i<LIMIT;i+=2){
		if(not_prime[i]==false)primes.push_back(i);
	}
	saiki(0,0,1);
	
	std::set<int>::iterator it=memo.begin();
	int num=(*it);
	int count=1;
	it++;
 	for(;it!=memo.end();it++){
		if(num+1==(*it)){
			count++;
			num++;
			if(count==4){
				printf("ans=%d\n",num-3);
				break;
			}
 		}else{
			num=(*it);
			count=1;
		}
	}
}