Problems dealing with prime numbers have always been of great interest to the programmers. One of the such problems is to generate all the prime numbers between any two Integers. The problems is very popular and finds its place in all the programming sites.
You have to generate all the prime numbers between two given integers x and y.
x < y <= 1000000000
y - x < 100000
So, the range of the numbers is quite large. Using the standard algorithms like Sieves won’t be a nice idea. The best solution to this problem is to use Sieve fo Eratosthenes with little modification to make that work for large numbers.
First of all, We will find and store all the prime numbers upto 31622. 31622 is the nearest integer to sqrt of 10^9.
To do this, We will use the following approach. I have intitialised an array with all the prime numbers upto 177(sqrt(31622) = 177.82).
After this, We will find out all the prime number upto 31622. To do that, We will apply Sieve of Eratosthenes for numbers upto 31622.
Let’s store all the prime numbers in an array prime.
The real magic will happen now. (Here,
upper is y and
lower is x).
Let us crack down the above code.
We will eliminate all the numbers from our list(given range) which are divisible by any of the prime numbers upto 31622.
So, for all the prime numbers, We will eliminate their multiples from the given range. For example, if the prime number is 31, we will eliminate the numbers 62, 93, 124 and so on.
m = prime[i] * 2 - lower finds the first number which is a multiple of
prime[i] in the given range.
lower + m is the first number which is a multiple of
Then, all the numbers in the given range are eliminated using the
while ( m < diff ) loop.
So, the numbers
lower + m,
lower + m + p[i],
lower + m + 2p[i] and so on are deleted.
In the end, we are left those numbers which are not divisible by any of the integers.
for loop can be used in this way to print the required numbers.
Here is the full source code of the solution written in C.
Any Comments or suggestions are welcome!