Executable on C++11/14/17
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.
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)))
using namespace std;
void SieveOfEratosthenes(int a,int b)
memset(prime, true, sizeof(prime));
for (int p=2; p*p<=b; p++)
if (prime[p] == true)
for (int i=p*p; i<=b; i += p)
prime[i] = false;
for (int p=a; p<=b; p++)
cout << p << " ";
cout<<"Enter the lower and upper range"<<endl;
cout<<"Prime numbers in given range are ";
Enter the lower and upper range
Prime numbers in given range are 5 7 11 13 17 19 23 29 31 37 41 43 47