c - C 中的素数生成器

Question

这是问题的链接:http://www.spoj.com/problems/PRIME1/

基本上我们有两个极限，我们必须打印出它们之间的所有素数...

这是我的代码(语言 == C):

#include <stdio.h>

void IsPrime(int test){
    for(int i= 2; i<test; i++){
        if(test%i==0){
            return;
        }
    }
    printf("%d\n",test);
}

int main(){
    int T,lower,upper;
    scanf("%d",&T);

    while(T--){
        scanf("%d",&lower);
        scanf("%d",&upper);

        for(int i = lower;i<=upper;i++){
            if(i>1){
            IsPrime(i);
            }
        }  
    }
return 0;
}

我在我的本地机器上运行了它，它适用于简单的测试用例...我从网站上收到的消息是超时错误，所以我想知道是否有更有效的方法来解决这个问题，因为显然我没有解决它够快吗？

Answer 1

首先，您不必检查直到 n 的每个数字来确定 n 是否为质数，只需检查它的平方根(有数学证明，现在不打算给出)。所以:

void IsPrime(int test){
    // i <= sqrt(test)
    // but to avoid sqrt you can do i * i <= test
    for(int i= 2; i * i <= test; i++){
        if(test%i==0){
            return;
        }
    }
    printf("%d\n",test);
}

接下来，我们知道在 2 之后，所有其他素数都是奇数，所以如果我们将 2 视为特殊情况，我们可以循环 2:

// Do greater than one check only once
if (lower > 1) {
    // Special case - lower is 2
    if (lower == 2) {
        printf("%d\n", 2);
        ++lower;
    }

    for(int i = lower; i <= upper; i += 2){
        IsPrime(i);
    }
}

---

但是，由于您必须执行 T 次，因此您最终会进行比需要更多的检查。此外，这个问题对 n 和 m 有限制，所以它基本上是完美的筛子，正如@HennoBrandsma 所说。

使用这些优化，您应该找到所有素数的极限，并将它们存储在容器中。然后，当提示范围时，只需遍历筛子并打印出数字。

(这将需要您稍微更改 IsPrime 函数 - 不要立即打印数字，让它返回 true 或 false，然后基于此将数字添加到容器中)