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

• Check if a number is prime
• Sieve of Eratosthenes

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[100001];

void SieveOfEratosthenes(int n){
	int p,j;
	
	// set all elements of prime[] to 1
	for(j=0;j<=n;++j)
		prime[j] = 1;
	
	prime[1] = 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[100001];
int prefix[100001];

void SieveOfEratosthenes(int n){
	int p,j;
	
	// set all elements of prime[] to 1
	for(j=0;j<=n;++j)
		prime[j] = 1;
	
	prime[1] = 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

Read
Right Shift Array by One (using 3 Methods)
Check if the given string is interleaving of two other strings