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)

Question

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

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

How can I make it more memory and time efficient ?

Input: the input begins with the number t of test cases in a single line (t <= 10).
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.
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;
}

The only even prime number is 2. Apart from that you can ignore even numbers. Hence, you do not need to test even divisors, `j` > 2. Test separately for 2 and then start your `j` loop at 3 and step 2 — rossum, Jun 20 '20 at 13:15
accessing the two dimensional array `test[][]` over and over and over` is a real time waster. Suggest only working with the two inputs of a single test case at a time — user3629249, Jun 21 '20 at 05:53
the value: `1000000000` is well within the limits of a `unsigned int` so suggest not using `long int` — user3629249, Jun 21 '20 at 05:54
there is nothing in your description of the problem about minimizing the memory consumed. Therefore, suggest writing a separate program to calculate all the primes from 2 through `10^9` and inserting the results into your 'test' program as `static const` data. Then the problem solution is a simple: loop through the prime data until one is found that is >= the start value, then output every value encountered until (but not including) the value exceeds the stop value — user3629249, Jun 21 '20 at 06:11
OT it is a very poor programming practice to include header files those contents are not used. Nothing in the posted code is using the contents of the header file: `stdlib.h` Suggest that header file be removed — user3629249, Jun 21 '20 at 06:18
Note: execution time and memory utilization are (almost) always a trade off. — user3629249, Jun 21 '20 at 06:29
@user3629249 "there is nothing in your description of the problem about minimizing the memory consumed." it's in the title, and also in the body: "How can I make it more memory and time efficient ?" — Will Ness, Jun 21 '20 at 13:45
I gave several ideas, in comments, about speeding up the code, because the execution time is limited. and, as I commented before, execution time and memory usage are a trade off, — user3629249, Jun 21 '20 at 16:03
What cpu type have you been given to ask to be under 6s? time limit has to be engaged to an architecture. — Luis Colorado, Jun 28 '20 at 09:53

Will Ness · Accepted Answer · 2020-11-01T16:22:25.973

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.

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.

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.

in the linked code, regarding: `// 1000 +: 9 13 19 21 31 33 39 49 51 61` 9, 21, 33, 49 are not prime So if that is an example of the output of the code, then the code is not correct. — user3629249, Jun 21 '20 at 05:42
@user3629249 you're misinterpreting the output. the numbers shown are deltas above the limit (here, 1000). that's what the `+` is hinting at. thus the primes are `1009, 1013, 1019, 1021, ...`. this is done for denser output, esp. with the very big limits. — Will Ness, Jun 21 '20 at 13:36

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)

1 Answers1

Linked