Prime Number Generator Time Limit Exceeded

Question

PRIME1- Prime Generator The code is working fine and it's generating a prime number from M to N but the only problem is I'm getting TLE when I submit my answer. How do I optimise my code to pass the time limit?

number-theory

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

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.

Example

Input: 2

1 10

3 5

Output:

2 3 5 7

3 5

Warning: large Input/Output data, be careful with certain languages (though most should be OK if the algorithm is well designed)

Time limit: 6s

Source limit: 50000B

Memory limit: 1536MB

#include <iostream>
#include <math.h>
#include <vector>

int main() {
int T;
uint64_t m, n;
std::scanf("%d", &T);
while (T--) {
    std::scanf("%llu %llu", &m, &n);

    std::vector<bool> flags(n+1);
    std::fill(flags.begin(),flags.end(),true);

    if (m == 1) {
        m++;
    }
    double halfMax = ceil(sqrt(n));
    for (uint64_t i = 2; i <= halfMax; ++i) {

        if (flags[i]) {
            for (uint64_t j = i * 2; j <= n; j += i) {
                flags[j] = false;
            }

        }
    }

    for (uint64_t k = m ; k <= n; ++k) {
        if (flags[k]) {
            printf("%lld", k);
            printf(" ");
        }

     }
     printf("\n");
   }
}

Answer 1

I see some things that may help you improve your code. I'll start with the stylistic pieces and then move on to the basic algorithm and the speed-up you're seeking.

Fix your formatting

This code has peculiar indentation that makes it difficult to tell when a function begins and ends. Fixing that would hlep.

Use <cmath> instead of <math.h>

The difference between the two forms is that the former defines things within the std:: namespace versus into the global namespace. Language lawyers have lots of fun with this, but for daily use I'd recommend using <cmath>. See this SO question for details.

Use all of the required #includes

The function std::scanf is used but its declaration is in #include <cstdlib> which is not actually in the list of includes. Similarly std::fill needs #include <algorithm>.

Avoid non-portable type assumptions

The code currently contains this line

std::scanf("%llu %llu", &m, &n);

That might be just fine with your compiler on your machine, but on mine, the compiler complains:

warning: format ‘%llu’ expects argument of type ‘long long unsigned int*’, but argument 2 has type ‘uint64_t* {aka long unsigned int*}’

The simplest way to avoid that problem is to use the C++ stream extractors instead:

std::cin >> m >> n;

There is a parallel problem (and fix) with std::printf.

Use the right constructor

The code currently contains these two lines:

std::vector<bool> flags(n + 1);
std::fill(flags.begin(), flags.end(), true);

Why not simply use the constructor version that does both of these?

std::vector<bool> flags(n + 1, true);

Use your knowledge of the mathematical domain

The only even prime number is 2, so you could optimize for both space and performance by only storing bits that correspond with odd numbers. Further, it's clear that if we eliminate even numbers, the inner sieve loop can look like this instead:

for (uint64_t j = i * i; j <= n; j += 2 * i) {

Avoid doing the same work twice

In the case that there are multiple trials, one simple optimization would be to compute the sieve only once (based on the largest n) and then simply use it multiple times rather than re-calculating the sieve for every trial.

Do work at compile time instead of runtime

Another optimization would be to compute the sieve at compile time rather than runtime. If you're using C++14 or better, one can compute the sieve at compile time.