SPOJ – Prime Generator

This is a neat question. The trick lies in the fact that primes are to be generated only within a particular range. I used a Eratosthenes sieve to generate primes <= sqrt(a limit), and stored it in a vector.

Now, there are three cases

1. The range is within the generated primes, ie the upper limit of range <= greatest prime already generated

2. The range is completely above the generated primes, ie the lower limit of range >= greatest prime already generated

3. Combination of 1 & 2

For case 1, simply loop through the vector and check if the number is there in the vector. For case 2, check divisibility by looping through all the generated primes.

Selecting the limit is the tricky part, depending on the range select a limit such that the execution time is minimal for a particular range provided.

As a optimization , notice that other than 2, all primes are odd, so every alternate number can be skipped if we start from 3. Similarly, multiples of 3, 5 and 7 occur in large numbers,so they can be rejected in the beginning itself [ of course, after initially marking them as prime].

Have fun!

Advertisements
Standard