Can anybody help me on the Prime Generator problem. I have been trying to use sieve method but I am not able to understand it. After reading http://www.codechef.com/viewsolution/1501682 solution of http://discuss.codechef.com/users/8377/amitupadhyay also I m not able to get it. Please do help?
Basically, the main point of understanding in this question is that, we cannot allocate the large memory the code requires and normal sieve won’t work. So, what to do in such case? Well, we have a pretty good concept of what is called segmented sieve.
It means, that we are making segments with the sieve we have. I once saved this text for future: "Say i need to find the prime numbers between 125 and 140 .One way is to find all primes till 140 using traditional sieves and then find how many of them are greater than 125.This will not work within limited time constraints.We need to fit the Sieve to our needs so that we run the Sieve only in that particular range.
The first prime is 2.We divide the starting number x=125 by 2 .We round off to smaller integer we get 62.We again multiply by 2 we get 124.What is 124 ?it is the first smaller number than x that is divisible by the prime 2.We start from 124,increment by 2 in each step and remove all elements between 125 and 140.That is we remove 126,128,130,132,134,136,138,140.What we did was that we did the first step in traditional sieve but just offset the starting elements to the closest composite number less than the starting point of the range.Next we do this with the 2nd smallest prime number 3.125/3=41.413=123.We start from 123 go till 140 (inclusive) in steps of 3 and cut the numbers 126,129,132,135,138.Next we do with 5.But from where do we get the prime numbers 2,3,5 and so on and how long do we need to do that? That can be done well by generating the sieve upto 10^6 which can be easily done". Hope it clears!!*
You may like referring my solution which proceeds exactly the same way my explanation above and is self- explanatory.
Also, following two may help more: