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

Paderewski

j times j < i times i - what is that supposed to do? – Sayles

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 – Latonya

regarding: ` for(i=0;i<t;i++){ //printf("Enter m,n:\n"); scanf("%ld %ld",&test[i][0],&test[i][1]); }` The program only needs to know about 2 values after reading t. Therefore, there is no need to keep all those values, suggest a simple loop, decrementing t until 0 and the body of the loop only has to work with the latest 2 values read from the input. Also, the functions: scanf() and printf() are VERY CPU intensive. Suggest using: getchar_unlocked() and putchar_unlocked() – Basseterre

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 – Basseterre

the value: 1000000000 is well within the limits of a unsigned int so suggest not using long int – Basseterre

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 – Basseterre

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 – Basseterre

regarding: ` for(j=2;jj<ii;j++){` This is a LOT of multiplying that is not needed. Suggest including math.h and calculate sqrt(i) into a separate variable, then using that separate variable similar to: int sqrt_n = sqrt( n ); for( j=3; j<=sqrt_n; j+=2 ) – Basseterre

Note: execution time and memory utilization are (almost) always a trade off. – Basseterre

@Basseterre "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 ?" – Predominant

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, – Basseterre

What cpu type have you been given to ask to be under 6s? time limit has to be engaged to an architecture. – Merbromin

Answer 1

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.

Predominant

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. – Basseterre

@Basseterre 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. – Predominant