UC知道杭电1239
来源：百度知道 编辑：UC知道 时间：2024/06/23 02:29:27
#include<iostream>
#include<cmath>
using namespace std;
int main()
{int i,j,max=0,flag=1,num=1,index1,index2,m;
double a,b,c[1229]={2};
while(scanf("%d%d%d",&m,&a,&b),m||a||b)//cin>>m>>a>>b&&a!=0||b!=0||m!=0)
{
for(i=3;i<=10000;++i)
{
for(j=2;j<=int(sqrt(double(i)))
;j++)
{if(i%j==0) flag=0;}
if(flag==1) { num++;
c[num]=i;
}
flag=1;
}
for(i=num;i>=0;--i)
{ for(j=i;j<num;++j)
{
if((c[i]/c[j])<(a/b) ||c[j]*c[i]>m || c[j]>m) break;
if(c[j]*c[i]>max)
{ max=c[j]*c[i];
index1=i;
index2=j;
}
}
}
max=0;
num=1;
cout<<c[index1]<<" "<<c[index2]<<endl;
}
return 0;
}
我的
#include<cmath>
using namespace std;
int main()
{int i,j,max=0,flag=1,num=1,index1,index2,m;
double a,b,c[1229]={2};
while(scanf("%d%d%d",&m,&a,&b),m||a||b)//cin>>m>>a>>b&&a!=0||b!=0||m!=0)
{
for(i=3;i<=10000;++i)
{
for(j=2;j<=int(sqrt(double(i)))
;j++)
{if(i%j==0) flag=0;}
if(flag==1) { num++;
c[num]=i;
}
flag=1;
}
for(i=num;i>=0;--i)
{ for(j=i;j<num;++j)
{
if((c[i]/c[j])<(a/b) ||c[j]*c[i]>m || c[j]>m) break;
if(c[j]*c[i]>max)
{ max=c[j]*c[i];
index1=i;
index2=j;
}
}
}
max=0;
num=1;
cout<<c[index1]<<" "<<c[index2]<<endl;
}
return 0;
}
我的
我改了你的代码，最终78ms过了
很明显的导致程序慢的代码是： for(j=2;j<=int(sqrt(double(i)));j++)
改成int len=int(sqrt(double(i)));for(j=2;j<=len;j++)
这样可以快上700ms。你外层循环次数多，而里面又多次调用sqrt(),double(),int()函数，导致耗时增多，何不定义个变量len，使它只做1次呢？
还有就是接下来的一句if(i%j==0) flag=0;
应该改成 if(i%j==0){ flag=0;break;}
若在循环中已经使flag=0，那么你余下的循环遍历又有什么用呢？所以在i%j==0成立的同时break掉，这样又大大提高了效率。
还有就是%d 对应int,%lf对应double
78MS AC代码如下：
#include<iostream>
#include<cmath>
using namespace std;
int main()
{int i,j,max=0,flag=1,num=1,index1,index2,m;
double a,b,c[1229]={2};
while(scanf("%d%lf%lf",&m,&a,&b),m||a||b)//cin>>m>>a>>b&&a!=0||b!=0||m!=0)
{
for(i=3;i<=10000;++i)
{
int len=int(sqrt(double(i)));
for(j=2;j<=len;j++) {
if(i%j==0) {flag=0;break;}
}
if(flag==1) {
num++;
c[num]=i;
}
flag=1;