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

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

Problem 347 「二つの素数で割り切れる最大の整数」 †

3162以上の素数と3162以上の素数は0。
3162以上の素数と3162以下の素数のケースはまとめて計算。
3162以下の素数と3162以下の素数の場合は全探索。

#include<stdio.h>
#include<map>
#include<vector>
#include<iostream>
#include<set>
#include<string.h>
#include<algorithm>
const int L=3162;
const int LIMIT=1000*10000;
bool isP[LIMIT+1];

std::map<__int64,__int64> memo;
std::vector<__int64> vec;

__int64 f(int p,int p2){
	__int64 ans=0,a1,b1;
	for(__int64 a=p;a<=LIMIT;a*=p){
		for(__int64 b=p2;a*b<=LIMIT;b*=p2){
			if(ans<a*b){
				ans=a*b;
				a1=a;
				b1=b;
			}
		}
	}
	//std::cout<<"("<<ans<<" "<<a1<<" "<<b1<<")";
	return ans;
} 

int main(){
	memset(isP,true,sizeof(isP));
	isP[0]=false;
	isP[1]=false;
	for(int i=2;i*i<=LIMIT;i++){
		if(isP[i]==false)continue;
		for(int j=i*2;j<=LIMIT;j+=i){
			isP[j]=false;
		}
	}
	for(int i=2;i<=LIMIT;i++){
		if(isP[i]){
			if(i>L){
				memo[i]=i;
			}else{
				vec.push_back(i);
			}
		}
	}
 	std::map<__int64,__int64>::iterator it,it2;
	__int64 sum=0;
	for(it=memo.begin();it!=memo.end();it++){
		sum+=(*it).second;
		(*it).second=sum;
	}
	memo[0]=0;
	__int64 ans=0;
	for(int i=0;i<vec.size();i++){
		__int64 a=vec[i];
		__int64 p=vec[i];
		while(a<=L){
			it=memo.upper_bound(LIMIT/a);
 			it--;
			it2=memo.upper_bound(LIMIT/(a*p));
			it2--;
			ans+=a*((*it).second-(*it2).second);
			a*=p;
		}
	}
	std::cout<<ans<<"\n";
	for(int i=0;i<vec.size();i++){
	for(int j=i+1;j<vec.size();j++){
			ans+=f(vec[i],vec[j]);
		}
	}
	std::cout<<"ans="<<ans<<"\n";
}