読者です 読者をやめる 読者になる 読者になる

日々精進

aikoと旅行とプログラミング

【AOJ 1232】Calling Extraterrestrial Intelligence Again

問題

Calling Extraterrestrial Intelligence Again | Aizu Online Judge

方針

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

コード

#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;
  }
}