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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s