## Problem Link

http://www.spoj.com/problems/PRIME1/

## Problem Description

In this problem, We need to print all the prime numbers between two given values m and n.

## Concepts Used

This problem is based on prime sieve(Sieve of Eratosthenes).

## Code

```
#include<stdio.h>
void sieve(long long int,long long int,bool[],bool[]);
int main()
{
long long int m,n;
int t;
/*scan number of test cases*/
scanf("%d",&t);
while(t--)
{
bool arr[100002]={0};
bool brr[100000]={0};
/*scan m and n */
scanf("%lld %lld",&m,&n);
/*call the function to mark all the prime number between m and n*/
sieve(m,n,arr,brr);
/*traverse arr[] and print all the unmarked entries*/
for(long long int l=m;l<=n;l+=1)
{
if((arr[l-m]==0)&&(l!=1))
printf("%lld\n",l);
}
printf("\n");
}
return 0;
}
void sieve (long long int m,long long int n,bool arr[],bool brr[])
{
/*j stores first even number to be marked*/
long long int j;
if(m%2==0)
j=m;
else
j=m+1;
if(j==2)
j+=2;
/*mark all the even numbers between a and b*/
while(j<=n)
{
arr[j-m]=1;
j+=2;
}
for(long long int i=3;i*i<=n;i+=2)
{
if(brr[i]==0)
{
long long int c=m%i;
long long int d;
/*d stores first multiple of i*/
if(c!=0)
d=m+i-c;
else
d=m;
/*marking starts from i*i or d whichever is maximum*/
if(d<(i*i))
d=i*i;
/*mark all the multiples of i starting from d(between m and n)*/
for(long long int j=d;j<=n;j+=i)
arr[j-m]=1;
}
/*mark all the multiples of i between 1 and sqrt(n)*/
for(long long int k=i*i;k*k<=n;k+=i)
brr[k]=1;
}
}
```

## Explanation

The aim is to find all the prime numbers between m and n. One simple method is to precompute all the prime numbers using prime sieve .Please read the post about prime sieve before reading this post.

But, **m** and **n** can have values up to **10^9** ,so we cannot simply implement this method for the given range and store all the prime numbers upto 10^9(we can have a bool array of size **10^8** max).

However, **range of n-m (n minus m) is upto 10^5**,so we can compute prime numbers between m and n for every test case using optimised version of sieve described in this post. The method is described as follows:

- For each test case,we have two arrays
`arr[]`

and`brr[]`

, both initialised with 0.`arr[]`

is used to mark the prime numbers between m and n,while`brr[]`

is used to mark the prime numbers upto 10^5.(Since maximum possible value of m and n is 10^9,we need to store prime numbers upto 10^5 only ,for marking all the primes) - In sieve earlier described,we start marking the even numbers starting from 4. However,in this case we start from the first even number after m.
- In the sieve method described,
`j`

starts from`i*i`

,however in this case ,we either start from`i*i`

or the`first multiple of i after m`

,whichever is maximum. - Once we have marked the primes between
**m**and**n**in`arr[]`

, we simply traverse`arr[]`

and print the primes(which have corresponding entries unmarked in`arr[]`

)

This content has been helpful to you?

Thanks for contributing!