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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20243
Problem 243 「弾性」 †
分数の弾性比率を求める問題。
計算時間1秒。
小さいほうから検討して計算するだけです。

#include<stdio.h>
#include<queue>


bool isPrime(int n){
	for(int i=2;i*i<=n;i++){
		if(n%i==0)return false;
	}
	return true;
}

struct E{
	double u,d;
	int p;
	bool operator<(const E& e1)const{
		return d>e1.d;
	}
};
 
int main(){
	const double LIMIT=15499.0/94744.0;
	std::priority_queue<E> pq;
	E e1;
	e1.u=1;
	e1.d=2;
	e1.p=2;
	pq.push(e1);
	while(pq.empty()==false){
		e1=pq.top();
 		pq.pop();
		if(e1.u/(e1.d-1)<LIMIT)break;
		
		E e2=e1;
		e2.u=e1.u*e1.p;
		e2.d=e1.d*e1.p;
 		pq.push(e2);
		int p2=e1.p+1;
 		while(isPrime(p2)==false){
			p2++;
 		}
		e2.u=e1.u*(p2-1);
		e2.d=e1.d*p2;
		e2.p=p2;
		pq.push(e2);
	}
	printf("%lf ans=%lf %lf %lf",e1.u,e1.d,e1.u/(e1.d-1),LIMIT);
}