Project Euler 71

nとdを正の整数として, 分数 n/d を考えよう. n

#include <iostream>
using namespace std;

int main(){
	const double a = (double)3/(double)7;

	double k1=0;
	int k2, k3;

	for(int i=1 ; i<1000000 ; i++){
		if(i%10000==0) cout << i << endl;
		for(int j=i/2 ; j>0 ; j--){
			if((double)j/(double)i<a){
				if((double)j/(double)i>k1){
					k1 = (double)j/(double)i;
					k2 = j;
					k3 = i;
					//cout << k2 << "/" << k3 << endl;
				}
				break;
			}
		}
	}

	cout << k2 << "/" << k3 << endl;
}

たぶん全探索する必要はなくて、1000000以下で最大の素数についての分母だけ調べればいいと思うんだけど、証明ができない。