Prime numbers in C++ |Code, and Explanation

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. Prime numbers are the building blocks of number theory. Mastering this topic can help you to perform well in Competitive programming contests. Let’s start without wasting time.

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

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:

The naive approach is very simple and straight forward. We will traverse a loop from 2 to N-1 and for each number itr we will divide N by itr, as a result, we will have two different cases.

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

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

We are tCraversing a loop of N-2 numbers therefore the time complexity is O(N).

Space Complexity

We have not taken any extra space therefore the space complexity is O(1).

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 1 sec we can perform 10^8 operations.

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

Since we are traversing a loop of √N values therefore the time complexity is O(√N).

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

Find all the prime numbers between 1 to 100?

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 prime or not. 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
prime numbers in c++
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

We have not taken extra space therefore the space complexity would be O(1).

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
prime numbers in c++
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 square root method. Therefore, the time complexity is O(N*√N).

Space Complexity

We have not taken any extra space therefore the space complexity would be O(1).

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++.

Leave a Comment

Your email address will not be published. Required fields are marked *