杭电1239

这是一道极其简单的搜索题目，不过简单归简单，对于刚入门的人来说，再简单的搜不是那么简单。所以这里还是写一下，希望可以帮助别人。

题目的大意是：

na.给定整数m,a,b(4< m <= 100000 and

  1<= a <= b <= 1000)

nb.需要找到两个数(不妨设为p,q)满足以下条件：

      p,q均为质数；

    p*q<=m;

    a/b <= p/q <= 1;

c.输出所有满足以上条件的p,q中乘积最大的一对p,q。

典型的想法是

从所有可能的p,q中寻找满足条件的一对

n2.p,q的要求

p,q均为质数,且p<=q<=100000;

n3.按上述思想流程应为：

a.从1—100000中搜出质数

b.两层循环，试遍所有的组合(p,q可能相等）

c.每种组合去判断是否符合条件，如是，将p*q与当前最大值比较，判断，保存。

不过这样肯定是会超时的，因为p，q的范围很大，那么我们自然而然就会想到我们应该将范围适当的压缩，也算是剪枝吧。

以下两种方法：

（1）

p,q的范围其实可在2—50000(why?) 然而，这是最小的范围吗？ 考虑大于10000的某个质数，不妨设为Q，另一个质数为P，则： 如果P<10，P/Q<0.001 如果P>10，P*Q>100000 而考虑到a,b的取值范围(1<=a<=b<=1000) 可知min(a/b)=0.001 同时，要求：p*q<=m<=100000 所以无论如何质数都不能超过10000 经过上面的数据的压缩，我们就可以直接来做了，首先找出10000以内的质数，应该不会超过2000，那么在这2000质数中采用暴力方法，一个一个搜索，最后求得最大的p*q; (2),我们知道对于p<=100000,q<=100000；但是p*q<=100000,这就直接让我们想到了开方，就是p，q必有一个大于sqrt（100000），另一个小于sqrt（100000），那么这下范围就收缩了很多，再采用暴力方法来找出满足题意的p和q。 我用的是第二种方法，下面附上一个代码：

#include
using namespace std;
#include
int main()
{int m,a,b,p,q,j,max;int p1,q1;double k1,k2;int leap1,leap2;while(cin>>m>>a>>b,m||a||b){leap1=0;leap2=0;max=j=0;k1=((double)a)/b;for(p=sqrt((double)m);p>=2;p--){for(int i=2;i<=sqrt((double)p);i++){if(p%i==0){leap1=1;break;}else leap1=0;}if(leap1==0){ for(q=p;q<=m/p;q++){for(int t=2;t<=sqrt((double)q);t++){if(q%t==0){leap2=1;break;}else leap2=0;}if(leap2==0){k2=((double)p)/q;if((k1<=k2)&&(k2<=1)){if(p*q>max){p1=p;q1=q;max=p*q;}}}}}}cout<<p1<<" "<<q1<<endl;}return 0;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！