假设输入可以达到 1000000000，我怎样才能编写一个更节省时间和内存的程序？ （打印 m 和 n 之间的所有素数）

Question

下面是代码（回答 CP 问题）

执行的时间限制是6秒，但我的代码比。

如何提高内存和时间效率？

• 输入：输入以单行中测试用例的数量t开始（t <= 10).

• 在接下来的 t 行中，每一行都有两个数字 m 和 n (1 <= m <= n <= 1000000000, n-m <= 100000) 由 space 分隔。

• 输出：对于每个测试用例，打印所有素数 p 使得 m <= p <= n , 每行一个数字，用空行分隔测试用例。

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    long int t,m,n,i,j,k;
    //printf("Enter number of testcases:\n");
    scanf("%ld",&t);
    long int test[t][2];
    for(i=0;i<t;i++){
        //printf("Enter m,n:\n");
        scanf("%ld %ld",&test[i][0],&test[i][1]);
    }
    
    for(k=0;k<t;k++){    
        for(i=test[k][0];i<=test[k][1];i++){
            for(j=2;j*j<i*i;j++){
                if(i%j==0)
                    break;
            }
            if(j==i){
                printf("%ld\n",i);
                }
            }
            printf("\n");
    }
    return 0;
}

Answer 1

使用offset sieve of Eratosthenes (see also this answer，带伪代码；这两个链接都是我的答案。

它是 segmented Eratosthenes 筛法，根据您的输入修改为仅适用于一个片段。

不同之处在于，分段 筛选无限期地按分段进行，并使用当前正在筛选的分段所需的尽可能多的素数（最多 它的上限的平方根）；这里顶部段的限制（以及核心段的限制）是预先知道的。

核心段延伸到要考虑的最大值的sqrt；这里给你的是10^9。 sqrt(10^9) < 32000，所以核心段跨越0到32000，并且被Eratosthenes的简单筛子筛分。

由于您有多个 运行，因此每个 运行 使用相同的内核。

链接答案中的代码很容易修改为这个问题的要求：不用估计 top 值，只需使用输入中提供给您的 n 即可。 above就是这里所说的m。