C++ Program to Print Prime numbers in a given range
Program to find Prime Numbers in a given range in C++
Here we will discuss how to find prime numbers in the range specified by the user using C++ programming language.
Prime numbers are the numbers which have 2 divisors only i.e. can be divided by 1 & itself Example: 2, 3, 5, 7, 11, 13 .... etc
In this program, the user will specify a range and we will check for every number in the range for being prime
Methods
We recommend going ahead with the codes on the page – Check if a number is prime or not in C++ before moving ahead with the methods below.
- Method 0: Check divisors between [2, n-1]
- Method 1: Check divisors between [2, n/2]
- Method 2: Check divisors between [2, √n]
- Method 3: Check divisors between [2, √n]. But, skipping even iterations.
Method 0
Concept used
For any number n. We will run a iterative loop between 2 to n-1. If there are divisors of the number in this range, then its not prime
Note : We will straight forward say 0,1 and negative numbers are not prime and handle those in for loop.
Note : We will straight forward say 0,1 and negative numbers are not prime and handle those in for loop.
C++ Code
Run
#include
using namespace std;
bool isPrime(int n){
int count = 0;
// 0, 1 negative numbers are not prime
if(n < 2)
return false;
// checking the number of divisors b/w 1 and the number n-1
for(int i = 2;i < n; i++)
{
if(n % i == 0)
return false;
}
// if reached here then must be true
return true;
}
int main()
{
int lower, upper;
lower=1,upper=100;
for(int i = lower; i <= upper; i++)
if(isPrime(i))
cout << i << " ";
}
// Time Complexity : O(N^2)
// Space Complexity : O(1)
Output
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Method 1
Concept used
For any number n. There would be no divisors in the range [n/2+1, n-1]
Example : For 33, numbers in the range(17, 32) won't divide 33.
Example : For 33, numbers in the range(17, 32) won't divide 33.
C++ Code
Run
#include <iostream>
using namespace std;
bool isPrime(int n){
int count = 0;
// 0, 1 negative numbers are not prime
if(n < 2)
return false;
// checking the number of divisors b/w 1 and the number n
for(int i = 2;i < n/2; i++)
{
if(n % i == 0)
return false;
}
// if reached here then must be true
return true;
}
int main()
{
int lower, upper;
lower=1,upper=100;
for(int i = lower; i <= upper; i++)
if(isPrime(i))
cout << i << " ";
}
// Time Complexity : O(N^2)
// Space Complexity : O(1)
Output
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Method 2
We recommend going ahead with the codes on the page – Check if a number is prime or not in C++ before moving ahead.
Concept used
For any number n. We can check of divisors in range [2, sqrt(n)], if we do not find any then its prime number
C++ Code
Run
#include <iostream>
#include <math.h>
using namespace std;
bool isPrime(int n){
int count = 0;
// 0, 1 negative numbers are not prime
if(n < 2)
return false;
// A number n is not a prime, if it can be factored into two factors a & b:
// n = a * b
/*Now a and b can't be both greater than the square root of n, since
then the product a * b would be greater than sqrt(n) * sqrt(n) = n.
So in any factorization of n, at least one of the factors must be
smaller than the square root of n, and if we can't find any factors
less than or equal to the square root, n must be a prime.
*/
for(int i = 2;i < sqrt(n); i++)
{
if(n % i == 0)
return false;
}
// if reached here then must be true
return true;
}
int main()
{
int lower, upper;
lower=1,upper=100;
for(int i = lower; i <= upper; i++)
if(isPrime(i))
cout << i << " ";
}
// Time Complexity : O(N√N)
// Space Complexity : O(1)
Output
Enter lower and upper ranges : 20 50
23 25 29 31 37 41 43 47 49
Method 3
We recommend going ahead with the codes on the page – Check if a number is prime or not in C++ before moving ahead.
Concept used
2 is the only even prime number, due to this fact we can skip all even iterations while checking for prime numbers.
C++ Code
Run
#include <iostream>
#include <math.h>
using namespace std;
bool isPrime(int n){
// 0 and 1 are not prime numbers
// negative numbers are not prime
if (n <= 1)
return false;
// special case as 2 is the only even number that is prime
else if (n == 2)
return true;
// Check if n is a multiple of 2 thus all these won't be prime
else if (n % 2 == 0)
return false;
// If not, then just check the odds
for (int i = 3; i <= sqrt(n); i += 2)
{
if (n % i == 0)
return false;
}
return true;
}
int main()
{
int lower, upper;
lower=1,upper=100;
for(int i = lower; i <= upper; i++)
if(isPrime(i))
cout << i << " ";
}
// Time Complexity : O(N^2)
// Space Complexity : O(1)
Output
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Other website’s Code
Some other websites have also given the following codes, which more as less give the same time complexity. But, are for no reason complex in code logic. We have still added them below so you can see all methods of prime numbers.Other website Method 1
Run
#include <iostream>
using namespace std;
int main ()
{
int lower=1, upper=100;
for (int i = lower; i < upper; i++){
if(i == 2){
cout << i << " ";
continue;
}
for (int j = 2; j < i; j++)
{
// if current i is divisible by any j
// i is not prime
if (i % j == 0)
break;
// if j reached i - 1
// we checked all numbers b/w [2, i-1] none are divisors
// thus number must be prime
else if (i == j+1)
cout << i << " ";
}
}
return 0;
}
Output
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 7
Other website Method 2
Below is complex for no reason. the explanation of this code is given later after the code below –#include
using namespace std;
int main () {
int lower, upper;
int i, j;
cout << "Enter lower and upper ranges : ";
cin >> lower >> upper;
// Note : Explanation for this code given below in another code
for(i = lower; i<upper; i++) {
if(i < 2)
continue;
for(j = 2; j <= (i/j); j++)
if(!(i%j))
break;
// if factor found, not prime
if(j > (i/j)) cout << i << ” “; } return 0; }
Output
Enter lower and upper ranges : 1 100 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Other website Method 2 (Explanation)
The explanation is added as comments
// This code is confusing and not ideal to code
// due its complex coding nature, what we have dicussed in previous
// methods is better and has same time complexity
#include<iostream>
using namespace std;
int main () {
int lower, upper;
int i, j;
cout << "Enter lower and upper ranges : ";
cin >> lower >> upper;
for(i = lower; i <= upper; i++) {
if(i < 2)
continue;
// why j <= (i/j)?
// Basically its same as j <= sqrt(i), which is
// critical boundary condition to check for prime number
// we can write j <= (i/j) as -> j * j <= i (multiplying by j on both sides)
// now apply sqrt on both sides it will become j <= sqrt(i)
for(j = 2; j <= (i/j); j++)
{
// why this ?
// its same as writing (i % j) == 0, we are just using not operator
if(!(i % j))
break;// if factor found, not prime
}
// why this?
// basically we are checking if sqrt(i) has become greater than i
// which would mean we have checked all numbers b/w 2 to sqrt(i)
// and found no divisors and thus it must be prime
if(j > (i/j))
cout << i << " ";
}
return 0;
}Output
Enter lower and upper ranges : 1 100 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
- Positive or Negative number: C | C++ | Java | Python
- Even or Odd number: C | C++ | Java | Python
- Sum of First N Natural numbers: C | C++ | Java | Python
- Sum of N natural numbers: C | C++ | Java | Python
- Sum of numbers in a given range: C | C++ | Java | Python
- Greatest of two numbers: C | C++ | Java | Python
- Greatest of the Three numbers: C | C++ | Java | Python
- Leap year or not: C | C++ | Java | Python
- Prime number: C | C++ | Java | Python
- Prime number within a given range: C | C++ | Java | Python
- Sum of digits of a number: C | C++ | Java | Python
- Reverse of a number : C | C++ | Java | Python
- Palindrome number: C | C++ | Java | Python
- Armstrong number : C | C++ | Java | Python
- Armstrong number in a given range : C | C++ | Java | Python
- Fibonacci Series upto nth term : C | C++ | Java | Python
- Find the Nth Term of the Fibonacci Series : C | C++ | Java | Python
- Factorial of a number : C | C++ | Java | Python
- Power of a number : C | C++ | Java | Python
- Factor of a number : C | C++ | Java | Python
- Strong number : C | C++ | Java | Python
- Perfect number : C | C++ | Java | Python
- Automorphic number : C | C++ | Java | Python
- Harshad number : C | C++ | Java | Python
- Abundant number : C| C++ | Java | Python
- Friendly pair : C | C++ | Java | Python
Login/Signup to comment
#include
using namespace std;
int main()
{
int n;
cin>>n;
for(int i=2;i<=n;i++){
int j;
for( j=2;j<i;j++){
if(i%j==0){
break;
}
}
if(j==i){
cout<<i<<endl;
}
}
return 0;
}
#include
using namespace std;
int main ()
{
int n, i, c = 0, count = 0;
for (n = 1; n <= 10; n++)
{
for (i = 1; i <=n; i++)
{
if (n % i == 0)
c++;
}
if(c==2)
{ count++;
//printf(" %d ",n);
cout<<" "<<n<=2)
c = 0;
}
printf (“The no of prime numbers = %d\n”, count);
return 0;
}
easy method
#include
using namespace std;
int main ()
{
int n, i, c = 0, count = 0;
for (n = 1; n <= 10; n++)
{
for (i = 1; i <=n; i++)
{
if (n % i == 0)
c++;
}
if(c==2)
{ count++;
//printf(" %d ",n);
cout<<" "<<n<=2)
c = 0;
}
printf (“The no of prime numbers = %d\n”, count);
return 0;
}