{{{ #!cplusplus /* hdu 1239 简单搜索+剪枝 ymc 2008/09/18 题目大意: 给定1<=m<=10000,1<=a<=b<=1000,求两个质数p,q 满足:p<=q,使得a/b<=p/q<=1,pq<=m,并且pq值最大。 分析鱼解题思路: 由pq<=m,得到p/q<=m/(q*q),结合a/b<=p/q<=1 得到q*q<=m*b/a,在有m,a,b的取值范围得到 q<=10000;同时2<=p<=q。 先求出10000以内的所有质数,然后对q,p从大到小搜索。 注意剪枝。 */ #include using namespace std; const int N=10000; bool flag[N]; int prim[N]={2}; int num=1; int m,a,b; void Init()//用伊拉脱森(Eratosthens)筛求质数 { memset(flag,1,sizeof(flag)); flag[0]=flag[1]=false; for(int i=0;i=0;i--) { q=prim[i]; if(q+q>m)//剪枝,p>=2 continue; if(q*q=0;j--) { p=prim[j]; tmp=p*q; if(tmp>m)//剪枝 continue; if(tmp<=Max)//剪枝 break; if(a*q<=b*p&&tmp>Max) { Max=tmp; p1=p; q1=q; } } } printf("%d %d\n",p1,q1); } int main() { Init(); while(scanf("%d %d %d",&m,&a,&b)) { if(m==0&&a==0&&b==0) break; Search(); } } }}}