下面两个程序的对比,为什么运行时间差这么多?

来源:百度知道 编辑:UC知道 时间:2024/06/01 09:25:11
#include<stdio.h>
#include<math.h>
void main()
{int m,n,i,k,s=0;
scanf("%d%d",&m,&n);
for(;m<=n;m=m++)
{k=sqrt(m);
for(i=2;i<=k;i++){
if (m%i==0)
break;}
if (i>=k+1)
s=m+s;
}
printf("%d\n",s);
}

运行要140ms

#include<stdio.h>
#include<math.h>
void main()
{
int a,b,k,i,j,m=0;
scanf("%d%d",&a,&b);
for(i=a;i<=b;i++)
{
k=sqrt(i);
for(j=2;j<=k;j++)
if(i%j==0)break;
if(j>k)m=m+i;
}printf("%d\n",m);}

这个只要 60ms
都是运行素数问题 算法一样,但是为什么运行时间差这么多?
我们做题都要考虑这个时间的,如果时间超时算我们错,很郁闷啊···

你可以把第一个程序中与第二个程序中不同的题目逐个改下,看看是哪个地方有影响.

第7行,m=m++,多了赋值操作
倒数第5行if (i>=k+1),与第二个程序相比,多了加法运算,>=和>也不知道有没有差别

if(j>k)m=m+i; 你把这句话放到循环里做 当然是不一样的咯

你好好看看那几句代码

问题就出在如果是素数的话,第二个的判别公式比第一个简单,第二个只是进行比较,而第一个先要计算再比较,后台操作时间长

第一个算法用了sqrt所以慢得很

要提高效率,则尽量少用乘法除法