该问题需要找到满足特定条件的素数对$(p, q)$，使得：

1. $p \times q \leq m$
2. $\frac{a}{b} \leq \frac{p}{q} \leq 1$
3. 在所有满足条件的素数对中，$p \times q$的值最大

代码实现主要分为以下几个步骤：

1. 素数筛选： • 使用埃拉托斯特尼筛法（Sieve of Eratosthenes）预处理$50000$以内的所有素数，存储在数组$b$中。

   • 时间复杂度：$O(n \log \log n)$，其中$n=50000$。

2. 枚举素数对： • 遍历所有素数对$(p, q)$，其中$p \leq q$（保证$\frac{p}{q} \leq 1$）。

   • 对于每个素数$p$，从$p$开始向后枚举素数$q$，直到$p \times q > m$或$\frac{p}{q} < \frac{a}{b}$。

   • 记录满足条件的素数对中$p \times q$的最大值。

3. 优化枚举范围： • 外层循环的枚举范围限制在$\sqrt{m}$以内，因为$p \leq \sqrt{m}$时$q$才能满足$p \times q \leq m$。

   • 内层循环在满足$p \times q \leq m$和$\frac{a}{b} \leq \frac{p}{q}$的条件下提前终止。

关键点说明

1. 素数筛选： • 预处理素数表$b$，避免每次查询重复计算。

   • 素数表的大小$50000$足够覆盖$m \leq 100000$的情况（因为$\sqrt{100000} \approx 316$）。

2. 条件判断： • 将分数比较$\frac{a}{b} \leq \frac{p}{q}$转化为整数乘法$a \times q \leq b \times p$，避免浮点数精度问题。

   • 优先枚举较小的素数$p$，并确保$p \leq q$以维持$\frac{p}{q} \leq 1$。

3. 提前终止： • 内层循环在$p \times q > m$或$\frac{p}{q} < \frac{a}{b}$时立即终止，减少不必要的计算。

代码实现

#include "iostream"
#include "cmath"
using namespace std;
 
int main()
{
	char a[50001]={0};
	unsigned short b[5135];
	
	int i,j;
	i=1;
	while(1)
	{
		while(a[++i]!=0);
		if(i>sqrt(50000.0)) break;
		j=i;
		while(1)
		{
			j+=i;
			if(j>50000) break;
			a[j]=1;
			
		}
	}
	int t=0;
	for(int k=2;k<=50000;k++)
	{
		if(a[k]==0) 
		{
			b[t++]=k;
			
		}
	}
	t--;
	
	
	while(1)
	{
		
		int m,aa,bb,tmparea;
		cin>>m>>aa>>bb;
		if(!m&&!aa&&!bb) return 0;
		
		int p=0,q=0,area=0;
		
		int len=(int)sqrt(100000.0)+1;
		for(int ii=0;b[ii]<=len;ii++)
		{
			for(int jj=ii;jj<=t;jj++)
			{
				tmparea=b[ii]*b[jj];
				if(tmparea<=m&&aa*b[jj]<=bb*b[ii])
				{
					if(tmparea>area)
					{
						p=b[ii];
						q=b[jj];
						area=tmparea;
					}
				}
				else
				{
					break;
				}
 
			}
		}
		cout<<p<<" "<<q<<endl;
	}
	return 0;
}