# C Program to Count Number of Prime Numbers in a Given Range

Write a program in c to count number of prime numbers in a given range.

For example,

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

Output
5```

Prerequisite Knowledge

## Naive Approach

Suppose we need 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. Use a counter to keep track of the number of prime numbers.

### Steps

1. Set n = L and c = 0.
2. Repeat following steps while n <= R
1. if n is prime, increment c.
2. increment n
3. Final answer is stored in c.
``````#include<stdio.h>
#include<math.h>
int main() {
int i,n,flag,c;
int l,r;

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

c = 0; // counter
// 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)
++c;

}

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

}``````

Output

Note: If you are confused about why we loop from 2 to sqrt(n) in the inner loop, then read the last section of this article.

## Efficient Approach: Sieve of Eratosthenes

Sieve of Eratosthenes creates an array such that if the ith element of the array is 1 then i is prime, and if the ith element of the array is 0, then i is not prime. We can directly check which number in the range [L, R] is prime using this array.

This method is very efficient if the range is large or the number of queries is very high.

``````#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,c;
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);

c = 0; // counter
// 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){
++c;
}

}

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

}``````

Output

## Efficient Approach: Sieve of Eratosthenes and Dynamic Programming

In the above program, to count prime numbers in the range [L, R], we are looping through every number from L to R. We can eliminate this loop using dynamic programming.

Let prime be the array obtained from Sieve of Eratosthenes. We will use another array prefix to store the prefix sum of prime.

``````for( i = 2; i<=n ; ++i )
prefix[i] += prime[i] + prefix[i-1]``````

The ith index of the prefix array gives the number of prime numbers from 1 to i. We can use the prefix array to count the number of prime numbers in [L, R] directly.

```prefix[L-1]: Number of Prime numbers from 1 to (L-1)
prefix[R]: Number of Prime numbers from 1 to R
prefix[R] - prefix[L-1]: Number of prime numbers from L to R```
``````#include<stdio.h>
#include<math.h>
#include<string.h>
int prime;
int prefix;

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 i;
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);

// creating prefix array of prime
for(i=2;i<=100000;++i){
prefix[i] = prime[i] + prefix[i-1];
}

printf("Number of Prime numbers between %d and %d are: %d\n",l,r,prefix[r]-prefix[l-1]);

}``````

Output