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

• Check if a number is prime or not

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

Read
Reverse String without String Function
Sieve of Eratosthenes
Different techniques to sort a 2D array