## Moment Of Primes

*Sift the Twos and sift the Threes,
The Sieve of Eratosthenes.
When the multiples sublime,
The numbers that remain are Prime*.

Applying Sieve of Eratosthenes a bit differently gives you solution to the primes generator problem in SPOJ(Sphere Online Programming Judge).

Here is how I did: Created 2 vectors, one of size sqrt(10^9) (named` lim_primes`

) and another of size 10^5 (named `primes`

). Applying the algorithm (above) I determined all the primes from 2 to sqrt(10^9). Got the user input in m(lower) and n(higher), both of data type long long int, as the higher bound is 10^9. Now if n is less than 32000, I can directly generate all primes using the former vector. Now m can be either less than 32000 (n > 32000) or more than 32000. If m is less than 32000, we already have primes in the interval [m, 32000). To generate primes in the range [32000, n], I picked a prime from `lim_primes`

, and *killed* all its multiples within the range [32000, n] in vector `primes`

, by creating an offset (= 32000/prime). Just a little thing, as offset is an integer and there might be numbers which do not give 0 on 32000%*number*, I checked if *number**offset is less than 32000 or not, if yes I incremented offset by 1. This (*killing* of numbers) is done by all primes within the range [2, sqrt(n)] in `lim_primes`

. Now to print numbers first traverse the `lim_primes`

from [m, 32000) then `primes`

from [32000, n].

This is the case when m is less than 32000, if m is more than or equal to 32000, replace 32000 in the above description by m. To print primes, only traverse the `primes`

vector (I don’t know why I am writing this!). According to SPOJ, the program’s run time is 0.19 seconds while its size is 2736KB. Here is the code.

Throughout the course of solving this problem, Yaani’s Until The Last Moment was in the air, and at one point I had tears in my eyes, its a lovely piece of music. Check it out on youtube, here. Hope you would love it :-).

Nice new look. ğŸ™‚

DDMay 18, 2009 at 13:49