【AOJ 1232】Calling Extraterrestrial Intelligence Again

問題

Calling Extraterrestrial Intelligence Again | Aizu Online Judge

方針

• とを満たすp, qを求める. (p, qは素数)
• エラトステネスの篩を使って素数を生成する.
• それらを使ってpとqの組を試す.
• qを求めるループの条件式は, という不等式から, とした.

コード

#include <bits/stdc++.h>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)

using namespace std;

#define MAX_M 100000

bool prime[MAX_M+1];

signed main(){
  int m, a, b;
  
  rep(i, MAX_M+2){
    prime[i] = true;
  }

  prime[0] = prime[1] = false;
  REP(i, 2, sqrt(MAX_M+2)){
    if(prime[i]){
      for(int j = i * 2 ; j <= MAX_M ; j+=i){
    prime[j] = false;
      }
    }
  }
  
  while(cin >> m >> a >> b, m || a || b){
    int ans_p, ans_q, ans_pq = -1;
    for(int p = 2 ; p <= m ; p++){
      if(!prime[p]) continue;
      for(int q = 2 ; q <= m/p ; q++){
    if(!prime[q]) continue;
    if(ans_pq < p * q && p * q <= m && (double)a/b <= (double)p/q && (double)p/q <= 1.0){
      ans_pq = p*q;
      ans_p = p;
      ans_q = q;
    }
      }
    }
    cout << ans_p << " " << ans_q << endl;
  }
}