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.

### Problem Statement

You have to generate all the **prime numbers** between two given integers **x** and **y**.

#### Constraints:

**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.
Actually, `lower + m`

is the first number which is a multiple of `prime[i]`

.

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.

A `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!