# C Program to Find Prime Numbers in a Given Range

Write a program in c to find prime numbers in a given range.

For example,

```Input
Lower Bound, L: 3
Upper Bound, R: 13

Output
Prime Numbers between 3 and 15 are:
3
5
7
11
13```

Prerequisite Knowledge

## Naive Approach

Suppose we want to find prime numbers in the range [L, R]. Simply loop through every number from L to R and check if the number is prime or not. If the number is prime, print it.

``````#include<stdio.h>
#include<math.h>
int main() {
int i,n,flag;
int l,r;

printf("Enter Lower Limit, L: ");
scanf("%d",&l);
printf("Enter Upper Limit, R: ");
scanf("%d",&r);

printf("Prime numbers between %d and %d are: \n",l,r);

// iterating all numbers from l to r
// and checking if they are prime or not
for(n = l;n<=r;++n){

// 1 is not prime
if(n==1)
continue;

// checking if n is prime or not
flag = 0;
for(i = 2;i<=sqrt(n);++i){
// if i divies n then it means n is not prime
// flag = 1 denotes that there exist a number
// between 2 and sqrt(n) that divides n
if(n%i==0){
flag=1;
break;
}
}

// flag = 0 implies no number divides n
// thus, n is prime
if(flag==0)
printf("%d\n",n);

}
}``````

Output

``````Enter Lower Limit, L: 3
Enter Upper Limit, R: 13
Prime numbers between 3 and 13 are:
3
5
7
11
13``````

Note: If you are confused about why we are iterating from 2 to sqrt(n) to check if n is prime or not, then read the last section of this article.

## Efficient Approach

The above program works fine if the range is small. But if the range is large or the number of queries is high then performance suffers. In that case, we can use Sieve of Eratosthenes.

Sieve of Eratosthenes creates an array such that if the pth index of the array is 1, then p is prime, and if the pth index of the array is 0, then p is not prime.

After creating the array using Sieve of Eratosthenes, we can directly print the prime numbers in the range [L, R] based on the array.

``````#include<stdio.h>
#include<math.h>
#include<string.h>
int prime;

void SieveOfEratosthenes(int n){
int p,j;

// set all elements of prime[] to 1
for(j=0;j<=n;++j)
prime[j] = 1;

prime = 0; // 1 is not prime
for(p=2;p<=sqrt(n);++p){
for(j=p*p;j<=n;j+=p){
prime[j] = 0;
}
}
}

int main() {
int n;
int l,r;

SieveOfEratosthenes(100000);  // sieve of eratosthenes up to 100000 numbers

printf("Enter Lower Limit, L: ");
scanf("%d",&l);
printf("Enter Upper Limit, R: ");
scanf("%d",&r);

printf("Prime numbers between %d and %d are: \n",l,r);

// iterating all numbers from l to r
// and checking if they are prime or not
for(n = l;n<=r;++n){

// if prime[n] = 1, then n is prime number
// if prime[n] = 0, then n is not prime
if(prime[n]==1){
printf("%d\n",n);
}

}

}``````

Output

``````Enter Lower Limit, L: 5
Enter Upper Limit, R: 27
Prime numbers between 5 and 27 are:
5
7
11
13
17
19
23``````