C语言求素数个数，交到oj上超时

Question

#include<stdio.h>
int main()
{
int K,a,b,i,n,is,m;
is=1;
m=0;
scanf("%d",&K);
while(K>0){
K--;
scanf("%d %d",&a,&b);
for(i=a;i<=b;i++){
is=1;
for(n=2;n<i;n++){
if(i%n==0){
is=0;
break;
}
}
if(is==1){
m++;
continue;
}
}
printf("%d\n",m);
}
return 0;
}

Answer 1

筛选法，供参考:

#include<stdio.h>
int num[1000002] = { 1,1,0 };
void Init()
{
    int i, j;
    for (i = 2; i <= 500000; i++) {
        if (num[i] == 0) {
            for (j = i + i; j <= 1000000; j += i) {
                num[j] = 1;
            }
        }
    }
}

int sum(int a, int b)
{
    int i, sum;
    for (i = a, sum = 0; i <= b; i++) {
        if (num[i] == 0)   sum++;
    }
    return sum;
}

int main() {

    int k, a, b, max, min;
    Init();
    scanf("%d", &k);
    while (k--) {
        scanf("%d %d", &a, &b);
        max = a > b ? a : b;
        min = a < b ? a : b;
        if (a == 0 && b == 0) 
                printf("0\n");
        else 
            printf("%d\n", sum(min, max));
    }
    return 0;
}