6
\$\begingroup\$

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");
   }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Regarding your performance: Don't do sieving each loop. Instead precompute all prime numbers from 2 to square root of 1000000000. Then simply test each prime until square root of input. C++ Stylistic comment: Prefer std::cin and std::cout over scanf and printf. \$\endgroup\$ – Maikel Mar 21 '17 at 10:53
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I'm also confused, why is that I can still use 'std::scanf' and 'std::fill' function even though I did not declare #include <cstdlib> and #include <algorithm> \$\endgroup\$ – Emmaaaaaaa Mar 22 '17 at 7:14
  • \$\begingroup\$ I did what you have suggested. It has greatly improved the overall performance but still, I'm getting TLE ( 9.637 secs ) maybe because my solution was not the right answer :( I also changed the inner sieve loop to what you have suggested for (uint64_t j = i * i; j <= n; j += 2 * i) but the output didn't turn out to be to what expected. Here is my [code]ideone.com/9dcCvf \$\endgroup\$ – Emmaaaaaaa Mar 22 '17 at 7:33
  • 1
    \$\begingroup\$ You omitted the most important optimization which is to only store odd numbers in the vector. Try this: ideone.com/SG7Hwv# \$\endgroup\$ – Edward Mar 22 '17 at 10:09
  • \$\begingroup\$ Also, see this new question, inspired by your question. \$\endgroup\$ – Edward Mar 22 '17 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.