c - 这是第二个 SPOJ Prime 生成器？谁能解释为什么它说错误答案？

Question

#include <stdio.h>
#include <stdlib.h>
int main(void) {
int tc=0,start=0,end=0,i=1,n=0,j=0;
char t[3],s[11],e[11];
scanf("%s",&t);
tc=atoi(t);
for(i=1;i<=tc;i++){
    scanf("%s %s",&s,&e);
    start=atoi(s);
    end=atoi(e);
    for(n = start;n <= end;n++){
        if(n==1) continue;
        if(n==2 || n==3) printf("%d\n",n);
        if(n%2==0 || n%3==0){
            continue;
        }
        for(j = 5; j * j < n; j+=6){
            if(n % j == 0 || n % (j+2) == 0){
                continue;
            }
        }
        printf("%d\n",n);
    }
    if(i!=tc)
    printf("\n");
}
return 0;
}

附注我不擅长 C，但我用 Python 实现了相同的程序，但它超出了时间限制。我也想知道这个问题是否可以用Python高效地解决。

Answer 1

几点:

1) 要将输入作为整数使用 scanf("%d",&tc)而不是

scanf("%s",&t);
tc=atoi(t);

2)用我在下面粘贴的代码替换您的内部循环。您的内部循环不会检查 5 的倍数。例如 5,55,95...

简单的算法是检查数字是否有因子直到sqrt(n)。如果是，则它是合数，否则是质数。

for(n = start;n <= end;n++){
if(n==1) continue;
int flag=1;
for(j=2;j*j<=n;j++){
if(n%j==0){
flag=0; //Is a factor
break;
}
}
if(flag)
printf("%d\n",n);
}