为什么程序老是超时,西电oj题目,我不懂什么时间复杂度,刚学C语言一学期
zyf最喜欢的数字是1!所以他经常会使用一些手段,把一些非1的数字变 成1,并为此得意不已。他会且仅会的两种手段是: 1.把某个数m除以某个质数p——当然p必须能整除这个数,即m=m/p
2.把某个数m减1,即m=m-1
有一天他突发奇想,想把[a,b]区间中所有的数一个一个地变成1,这是一个巨大的无聊的工程,所以他想知道他最少得花多少操作才能达到目 的。
Input 输入包含多组数据(1000组数据),EOF结束。
每组数据以两个整数开头:a,b(0<a<=b<=100000),意义如题意描述。Output 每组数据输出一行,最少操作数。Sample Input2 3
3 5
11 12Sample Output2
4
3
以下是我的程序
#include<stdio.h>
int isprime(int x)
{
int i;
if(x==2)
return 1;
else for(i=2;i<x;i++)
if(x%i==0)
return 0;
return 1;
}
int main()
{
int a,b,i,sum,temp;
while(scanf("%d %d",&a,&b)!=EOF)
{
if(a>b)
{
i=a;
a=b;
b=i;
}
sum=0;
for(i=a;i<=b;i++)
{
temp=i;
while(temp!=1)
if(isprime(temp))
{
sum++;
temp=1;
}
else
{
sum++;
temp--;
}
}
printf("%d\n",sum);
}
return 0;
}
求大神指教,怎么改,谢谢