Segmented Sieve Algorithm

[Impervious] : This algorithm can be used to check for prime numbers up to 10^14 in a given range [ m , n ], as large as 10^7. For example, it can be used to check for prime numbers in [ 10^5 ,10^6 ]. The essence of the algorithm lies in the fact that the square root of the largest 14-digit prime will be less than the largest 7-digit prime. The algo. is as follow : First store all primes up to 10^7 in an array(say primes[]), using simple sieve. Now based upon the input, proceed as follows :

1. If n < 10^7 , simple iterate and print the primes, stored in the array.

2. If m > 10^7 , then first declare an array of size n-m(this can also be declared initially as test_range[10^7] ). Now for each prime in primes, strike out all multiples of it in the range(that is , mark all multiples of primes[i] in test_range[] as composite , as we do in simple sieve). Note that the first element of test_range corresponds to m , the second to m+1, and so on , the last to n. Finally , print the remaining elements of the test_range.

3. If m is less than 10^7 and n is greater than 10^7, a combination of the above two,split the range. Damn simple.

Note that, we can only check the prime numbers in a given range and not store them.

I`ll be posting the code a little later.
Happy coding!!!