Joy precedes competition.

Game && Jaguareins

Moment Of Primes

with one comment

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 :-).

Advertisements

Written by LaFolle

May 12, 2009 at 09:31

Posted in Uncategorized

Tagged with ,

One Response

Subscribe to comments with RSS.

  1. Nice new look. 🙂

    DD

    May 18, 2009 at 13:49


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

%d bloggers like this: