Problem 1232 : Calling Extraterrestrial Intelligence Again

Problem A: Calling Extraterrestrial Intelligence Again
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1232

• 問題概要

整数m, a, bが与えられる。
素数p, qのうち、
p*q <= m && a/b <= p/q <= 1
であるもので最大のp*qになるような素数p*qを答えなさい。

• 解法

p*qを決める。
p*qをｍから減らしていって、そのp*qの値になるようなp*qが存在するか調べる。
pをループ回すと、pに対するqはひとつに定まる。
そのあと、a/b <= p/q <= 1になるか調べる。
最初に見つかったものが答え。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

#define N 100000

using namespace std;


main(){

  int p[N];
  rep(i, N)p[i] = true;
  p[0] = p[1] = false;
  rep(i, N){
    if(!p[i])continue;
    for(int j=2; j*i < N; j++){
      p[i*j] = false;
    }
  }
  
  int m, a, b;
  while( cin >> m >> a >> b){
    if(m + a + b == 0)break;
    for(int i=m; i>=0; i--){
      bool found = false;
      for(int j = 2; j*j<=i; j++){
	if(i%j != 0)continue;
	if(!p[j] || !p[i/j])continue;
	if(((double)a/b) > ((double)j/(i/j)))continue;
	cout << j << ' ' << i/j << endl;
	found = true;
	break;
      }
      if(found)break;
    }
  }
}