I am trying to solve Prime Generator problem and using the sieve of erasthones Algorithm to finding the prime number between two number of large range (m and n (1 <= m <= n <= 1000000000, nm<=100000) ) and getting RunTime Error related to memory i.e. due to large number the array index fails. Please anyone help me how to use sieve of erasthones Algorithm for this problem.
link of the solution.link text Thanks in advance asked 26 Dec '12, 20:31

Give the number m , index 0 and the number n , index nm. Your algorithm will not terminate in time because you are running a loop from 0 to end ( end = n ) . n is about 10^9 also . The way to solve this problem is : 1. Find all primes till 32000 by Sieve method . 2. Mark all numbers between m and n as prime . Then use sieve to mark numbers as not prime using primes found in step 1 only . Note : A number is not divisible by any prime greater than its square root unless it is prime itself , and hence divisible by itself . answered 26 Dec '12, 21:21

you can see my solution , its easy to understand http://www.codechef.com/viewsolution/6806867 answered 22 Apr '15, 23:07

Clearly n is <=10^9 so sqrt(n)~32000 so you can improve the complexity with some preprocessing. Preprocess prime numbers less than 32000. Now to check any number whether it's prime or not,one of its divisors must be always less than its square root. Using this property I can say lets check each number whether it's divisible by a number less than its square root.Below is the link to my solution in C++. answered 16 Apr '17, 17:03

for larger values and input your code is giving the error answered 16 Apr '17, 23:46
