c语言求素数个数，优化方法

Question

以下是题目和我写的代码，但是超时了，谁有更优化的方法吗，求解

/*给定两个非负整数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;
}

Answer 1

素数优化算法http://blog.csdn.net/liukehua123/article/details/5482854

 #include<stdio.h>
#include<math.h>
#define N 10000001
bool prime[N];
int main()
{
   int i, j;
   for(i=2; i<N; i++)
  if(i%2) prime[i]=true;
  else prime[i]=false;
   for(i=3; i<=sqrt(N); i++)
   {   if(prime[i])
       for(j=i+i; j<N; j+=i) prime[i]=false;
   }
   for(i=2; i<100; i++)//由于输出将占用太多io时间，所以只输出2-100内的素数。可以把100改为N
    if( prime[i] )printf("%d ",i);

   return 0;
}