鉴于输入可以高达 1000000000，我该如何编写更省时省内存的程序?(打印 m 和 n 之间的所有素数) [英] Given that the inputs can be up to 1000000000, how can I write a more time and memory efficient program? (print all primes between m and n)

问题描述

这是下面的代码(针对 CP qs)

Here is the code below (ans to a CP qs)

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

The time limit for execution is 6 seconds but my code is slower than.

我怎样才能让它更有内存和时间效率?

How can I make it more memory and time efficient ?

• 输入:输入以一行中t个测试用例的数量开始(t <= 10).

• Input: the input begins with the number t of test cases in a single line (t <= 10).

在接下来的每一行 t 中有两个数字 m 和 n(1 <= m<= n <= 1000000000, nm <= 100000) 以空格分隔.

In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m <= 100000) separated by a space.

输出:对于每个测试用例打印所有质数p，使得m <= p <= n，每行一个数字，测试用例以空行分隔.

Output : for every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

#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;
}

推荐答案

使用埃拉托色尼的偏移筛(另见这个答案，带有伪代码；两个链接都是我的答案).

Use offset sieve of Eratosthenes (see also this answer, with pseudocode; both links are to SO answers by me).

这是一个分段的埃拉托色尼筛，根据您的输入修改为仅适用于一个分段.

It is a segmented sieve of Eratosthenes modified to work on only one segment, as per your inputs.

区别在于分段筛分无限期地按段进行，并根据当前被筛分的段(最多其上限的平方)使用尽可能多的素数根);在这里，顶部细分市场(以及核心细分市场)的限制是预先知道的.

The difference is that a segmented sieve proceeds by segments indefinitely and uses as many of the primes as needed by the segment currently being sieved (up to its top limit's square root); here the top segment's limit (and hence the core segment's) is known upfront.

核心段延伸到要考虑的最大值的sqrt；这里以 10^9 形式提供给您.sqrt(10^9) <32000，所以核心段跨度为0~32000，用Eratosthenes的简单筛法进行筛分.

The core segment extends up to the sqrt of the biggest value to be considered; here it is given to you as 10^9. sqrt(10^9) < 32000, so the core segment spans 0 to 32000, and is sieved by the simple sieve of Eratosthenes.

由于您有多次运行，因此每次运行都使用相同的核心.

Since you have several runs, use the same core for each run.

链接答案中的代码很容易根据此问题的要求进行修改:无需估计 top 值，只需使用输入中提供给您的 n 值即可.above 就是这里的m.

The code in the linked answer is easily amended to this question's requirements: instead of estimating the top value, just use the n supplied to you in the input. above is what's called m here.

这篇关于鉴于输入可以高达 1000000000，我该如何编写更省时省内存的程序?(打印 m 和 n 之间的所有素数)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！