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