C++ Program to Display Prime Numbers Between Two Intervals














































C++ Program to Display Prime Numbers Between Two Intervals



Executable on C++11/14/17
Description:
A prime number is a number that is divisible by 1 and itself.For example 2,3,5,7,11 etc.
A simple approach to this problem will be to run a for loop from the smaller number(say,a) to the larger number(say,b) and check each number for prime and display the number if found as prime.However in this case the time complexity will be the order of n^2.We can reduce the time complexity of the program by using the logic of "Sieve of Eratosthenes".

The Sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million or so.It is a method of finding all primes numbers lower than the given limit.For example if we enter the number 100,it generates all prime numbers between 2 and 100.
Approach:
Here is an algorithm to find prime numbers between the given range using Sieve Of Eratosthenes method:
1. Create a list of numbers from 2 to maximum value.
2. Initially, let p equal 2, the first prime number.
3. Starting from p^2, count up in increments of p and mark each of these numbers greater than or equal to p^2 itself in the list. These numbers will be p(p+1), p(p+2), p(p+3), etc.
4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.
5.We have the list of numbers that are prime in range of 2 to maximum value and now we can just limit out the numbers,i.e,we can run a for loop from a to b and print all prime numbers.

The time complexity using this approach is:O(n*log(log (n)))

Program:
#include <bits/stdc++.h>
using namespace std;
//function to check whether the number is prime or not
void SieveOfEratosthenes(int a,int b)
{
//Create an array of boolean numbers prime[] and set it to "True"
//If finally the value of prime[i] remains true then it is prime else it is not.
bool prime[b+1];
memset(prime, true, sizeof(prime));

for (int p=2; p*p<=b; p++)
{
// If prime[p] is not changed, then it is a prime
if (prime[p] == true)
{
// Update all multiples of p greater than or equal to the square of it
// numbers which are multiple of p and are less than p^2 have already been marked.
for (int i=p*p; i<=b; i += p)
prime[i] =
false;
}
}

// Print all prime numbers in the range of a to b.
for (int p=a; p<=b; p++)
if (prime[p]==true) //if the index is still assigned as true then print the number
cout << p << " ";
}

// Driver Program to test above function
int main()
{
int a,b;
cout<<"Enter the lower and upper range"<<endl;
cin>>a>>b;
cout<<"Prime numbers in given range are ";
SieveOfEratosthenes(a,b);
return 0;
}

Output:
Enter the lower and upper range
5 50
Prime numbers
in given range are 5 7 11 13 17 19 23 29 31 37 41 43 47


Comments