Here we will learn different algorithms to calculate ** prime numbers in c++**. This topic is super popular in competitive programming, as many questions were asked on competitive programming websites.

**are the building blocks of**

*Prime numbers***. Mastering this topic can help you to perform well in Competitive programming contests. Let’s start without wasting time.**

*number theory*Table of Contents

*What are the prime numbers?*

*What are the prime numbers?*

** Prime numbers** are the natural numbers greater than 1 that have only two factors 1 and itself the number. A natural number that is greater than 1 and not prime is called a

*composite number.*Examples of prime numbers: 2, 3, 5, 7, 11, 13, 17, etc.

*Some amazing facts about prime numbers:*

*Some amazing facts about prime numbers:*

is the only prime number that is even.*Two*- All the prime numbers can be represented in the form of
or*6n-1*except 2 and 3, where n is a natural number.*6n+1* and*Two*are the only consecutive natural numbers that are prime too.*Three*- No
greater than 5 ends in a 5.*prime number*

*How to check if the given number is prime or not?*

*How to check if the given number is prime or not?*

Here we will be given a number ** N **we need to check whether the number is prime or not. There are many methods to solve this problem. We will be discussing here every possible method one by one. (prime numbers in C++)

*Method 1) Naive Approach:*

*Method 1) Naive Approach:*

The naive approach is very simple and straight forward. We will traverse a loop from 2 to ** N**-1 and for each number

**we will divide N by**

*itr***, as a result, we will have two different cases.**

*itr*- If the
divides N then N is not a prime number.*itr* - Otherwise, we will keep traversing till
-1. If we finished the loop then that means*N*is a prime.*N*

Let’s implement this method.

```
#include<bits/stdc++.h>
using namespace std;
//driver code
int main()
{
int N;
cout<<"Enter input:";
cin>>N;
bool prime = true; // intially we assume the number is prime
// loop from 2 to N-1
for( int itr = 2; itr < N; itr++)
{
if(N % itr == 0)
{
prime = false;
break;
}
}
if(prime)
{
cout<<N<<" "<<"is a prime number";
}
else
{
cout<<N<<" "<<"is not a prime number";
}
}
```

Check the code here

*Time Complexity*

*Time Complexity*

We are tCraversing a loop of ** N**-2 numbers therefore the

**is**

*time complexity***.**

*O(N)**Space Complexity*

*Space Complexity*

We have not taken any extra space therefore the ** space complexity** is

**.**

*O(1)**Limitations*

*Limitations*

This method is not an efficient method as it fails when the value of ** N** is greater than 10^8 here we assume that in

**we can perform 10^8 operations.**

*1 sec**Method 2) Square root method*

*Method 2) Square root method*

The previous method fails for values greater than 10^8. This method is very popular in competitive programming as many tough questions need this little optimization to get the correct output. Let’s learn this optimized method.

This methods says:

- We don’t need to check for all the values from 2 to N-1. We just need to check till √N values because at least one of the factors of N must be less than √N.
- Now, we will traverse a loop from 2 to √N.
- This method works fine for values less than or equal to 10^16.
- We can do another optimization in this method:
- Right now, we are traversing all values from 2 to √N but if we observe carefully then we will see that we don’t need to check for the even numbers as if the number is not divisible by 2 then it won’t divisible by any other even number. Therefore, we only check for 2 and then for every odd number.

Let’s implement this method

```
#include<bits/stdc++.h>
using namespace std;
//driver code
int main()
{
int N;
cout<<"Enter input:";
cin>>N;
bool prime = true; // initially we assume the number is prime
if(N % 2 == 0) // to check if the number is even or not
{
prime = false;
}
else
{
for(int itr = 3; itr * itr <= N; itr+=2) // This itr +=2 will make sure that the next value will be an //odd value
{
if(N % itr == 0)
{
prime = false;
break;
}
}
}
if(prime)
{
cout<<N<<" "<<"is a prime number";
}
else
{
cout<<N<<" "<<"is not a prime number";
}
}
```

*Time Complexity*

*Time Complexity*

Since we are traversing a loop of ** √N** values therefore the

**is**

*time complexity***.**

*O(√N)**Space Complexity*

*Space Complexity*

We have not taken any extra space therefore the ** space complexity** is

**.**

*O(1)*Now, let’s solve a problem based on the above methods we discussed.

*problem statement*

*problem statement*

*Find all the prime numbers between 1 to 100?*

*solution*

*solution*

The solution to this problem is very simple. Here, we will traverse all the numbers between 1 to 100, and for each number, we will apply ** any of the methods** discussed above to check if the number is

**or not.**

*prime***.**

*Let’s implement the solution**Using Method 1:**Naive approach*

```
#include<bits/stdc++.h>
using namespace std;
bool isPrime(int n)
{
if(n==1)
{
return false;
}
else
{
for(int i = 2; i<n; i++)// naive appraoch
{
if(n%i == 0)
{
return false;
}
}
return true;
}
}
int main()
{
cout<<"Prime numbers between 1 and 100 are: ";
for(int i = 1; i<=100; i++)
{
if(isPrime(i))
{
cout<<i<<" ";
}
}
return 0;
}
```

*Output*

*Output*

*Time Complexity*

*Time Complexity*

Here we are traversing a loop of 100 numbers and for each number, it takes O(N) time to check if it is prime or not. Therefore the time complexity would be ** O(N*100)** since 100 is constant hence the time complexity is

**.**

*O(N)**Space Complexity*

*Space Complexity*

We have not taken extra space therefore the ** space complexity** would be

**.**

*O(1)**Limitation*

*Limitation*

For this problem, the above code will work well but if the upper limit is greater than 10^4 then this code fails. The** time complexity **for the values greater than 10^4 will be more than 10^8 which is not acceptable.

** To solve the problem for the values greater than 10^4 we will use method 2**.

*Using Method 2: Square root method*

Here also we will traverse a loop from** 1 to N** and we will apply the prime check to each number but here we will use

**.**

*method 2*Let’s implement this method.

```
#include<bits/stdc++.h>
using namespace std;
bool isPrime(int n)
{
if(n==1)
{
return false;
}
else if(n%2 == 0)
return false;
else
{
for(int i = 3; i*i<=n; i+=2)// naive appraoch
{
if(n%i == 0)
{
return false;
}
}
return true;
}
}
int main()
{
int N;
cout<<"Enter the upper limit:";
cin>>N;
cout<<"Prime numbers between 1 and "<<N<<" are: ";
for(int i = 1; i<=N; i++)
{
if(isPrime(i))
{
cout<<i<<" ";
}
}
return 0;
}
```

Check the code here

*Output*

*Output*

*Time Complexity*

*Time Complexity*

Here we are traversing a loop of** N **numbers and checking each number if it is prime or not and for that,

**we are using the**

**. Therefore, the**

*square root method***is**

*time complexity***.**

*O(N*√N)**Space Complexity*

*Space Complexity*

We have not taken any extra space therefore the ** space complexity** would be

**.**

*O(1)**Conclusion*

*Conclusion*

- We have discussed the two most basic methods that can be used to solve this problem.
- We can further improve the prime check by using some standard algorithms like:
*Sieve of Eratosthenes**Segmented sieve*

- There are also some important theorems based on prime numbers like:
*Wilson Theorem**Fermat’s Little Theorem*

Hope you like this article on *prime numbers in c++.*