以下是题目和我写的代码,但是超时了,谁有更优化的方法吗,求解
/*给定两个非负整数a,b,其中0<= a,b<=1,000,000,请计算这两个数之间有多少个素数。
输入
第一行是一个整数K(1<=K<=1000),表示有多少个样例,每个样例占一行,是两个整数a和b,每个整数之间用一个空格隔开。
输出
每行输出一个样例的结果。
Sample Input
2
2 3
17 19
Sample Output
2
2*/
#include
#include
int main()
{
int n,i,j,a,b,sq;
scanf("%d",&n);
while(n--)
{
int sum=0;
scanf("%d %d",&a,&b);
if(a>b)
{
int temp=a;
a=b;
b=temp;
}
for(i=a;i<=b;i++)
{
sq=sqrt(i);
for(j=2;j<=sq;j++)
if(i%j==0)
break;
if(j>sq)
sum++;
}
if(a==1||a==0)
sum--;
printf("%d\n",sum);
}
return 0;
}