AOJ1232 Calling Extraterrestrial Intelligence Again

問題リンク Calling Extraterrestrial Intelligence Again

• 概要

m, a, bの3つの値が与えられる。
2つの素数の組p, qを
p*q<=m
a/b <= p/q <= 1
を満たすものとするとき、p*qを最大にするようなp, qを答えよ
4 < m < 10^5
1 <= a <= b <= 1

• 解法

エラトステネスの篩で10^5までの素数を求めておきます。
p*qの積Xを固定し、素因数を1つ見つけpとします。
qをX/pとし、このqも素数であり、a/b<=p/q<=1を満たすのならば、このpとqが答えです。
a/b<=p/q<=1の判定にa/bの値とp/qの値を使うのはあまり嬉しくないので、式変形して
p<=q
a*q<=b*p
の2つを満たしているかで判定した方がいいと思います。これなら浮動小数点が現れず、整数計算だけで判定できます。

• ソース

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

//Calling Extraterrestrial Intelligence Again
public class AOJ1232 {

	void run(){
		Scanner sc = new Scanner(System.in);
		int N = 100000;
		boolean[] f = new boolean[N+1];
		Arrays.fill(f, true);
		List<Integer> sieve = new ArrayList<Integer>();
		f[0]=f[1]=false;
		for(int i=2;i<=N;i++)if(f[i]){
			sieve.add(i);
			for(int j=i+i;j<=N;j+=i)f[j]=false;
		}
		int n = sieve.size();
		for(;;){
			int m = sc.nextInt(), a = sc.nextInt(), b = sc.nextInt();
			if((m|a|b)==0)break;
			boolean con = true;
			for(int x=m;x>0;x--){
				if(!con)break;
				for(int ip=0;ip<n;ip++){
					int p = sieve.get(ip);
					if(p*p>x)break;
					int q = x/p;
					if(x%p!=0||p*b<q*a)continue;
					if(f[q]){
						con = false;
						System.out.println(p+" "+q);
						break;
					}
				}
			}
		}
	}
	
	public static void main(String[] args) {
		new AOJ1232().run();
	}
}