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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20234
Problem 234 「半分割可能数」 †
999966663333を越えない半分割可能数を求める問題。

順番に並んだ素数,p1,p2にたいしp1^2<n<p2^2の間にある数を考え。
nをp1^2のほうからみて割れる数とnをp2^2のほうから見て割れる数とをadd1,add2としてたし
ｐ１、ｐ２で重複する数を考えてそれをdell3として（重複しているので2倍）引く。
後はキリの悪い999966663333より大きな数は力技で引くだけです。

試行錯誤時間15分
コード実装時間10分。
計算時間1分

#include<stdio.h>
#include<map>
#include<vector>
#include<iostream>
#include<set>
#include<math.h> 
const __int64 L=999983;
const __int64 LIMIT=999966663333;

bool isPrime(__int64 p){
	if(p<2)return false;
	if(p==2)return true;
	for(__int64 i=3;i*i<=p;i+=2){
		if(p%i==0)return false;
	}
	return true;
}
std::vector<__int64> ps;
 
int main(){
	__int64 p=1;
	ps.push_back(2);
	while(p<L){
		p+=2;
		while(isPrime(p)==false){
			p+=2;
		}
		ps.push_back(p);
	}
	__int64 ans=0;	
 	std::cout<<"a\n";
	for(int i=0;i+1<ps.size();i++){
		if(i%100==0){
			printf("%d/%d\n",i,ps.size());
		}
		__int64 p1=ps[i];
		__int64 p2=ps[i+1];
		__int64 d=p2*p2-p1*p1-1;
		__int64 d1,add1,d2,add2,dell3,p3,d3;
		d1=d/p1;
 		add1=p1*p1*d1+p1*(d1*(d1+1))/2;
		d2=d/p2;
		add2=p2*p2*d2-p2*(d2*(d2+1))/2;
		p3=p1*p2;
		d3=(p2*p2-p3-1)/p3;
 		dell3=p3*(d3+1)+p3*(d3*(d3+1))/2;
		ans+=(add1+add2-2*dell3);
	}
	__int64 p1=ps[ps.size()-2];
	__int64 p2=ps[ps.size()-1];
	for(__int64 i=LIMIT+1;i<p2*p2;i++){
		if((i%p1==0)&&(i%p2!=0)){
			ans-=i;
		}else if((i%p1!=0)&&(i%p2==0)){
			ans-=i;
		}
	}
	std::cout<<"\nans="<<ans;
}