C++ Program to Check Prime Number

Write a C++ program to check if a given number is Prime number or not.

A prime number is a natural number greater than 1 that can only be divided by 1 and itself without leaving a remainder.

Examples of Prime Numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23 …., etc.

1. The number to be checked is entered.
2. If it is divisible by any natural number from 2, then is it is not a prime number.
3. Else it is a prime number.
4. The result is printed.
5. Exit.

There are several ways to write a prime number program in C++. Let’s look at all different techniques to write a prime number program.

• C++ Program to Check Prime Number using Loops (Naive Approach)
• C++ Program to Check Prime Number using Optimized Approach
• C++ Program to Generate Prime Numbers Using Sieve of Sundaram

In this approach, we determine whether the given number is prime or not by using if-else statements.

Here is the source code of C++ Program to Check if a Number is Prime. The program output is shown below.

/*
 * C++ Program to Check Prime Numbers
 */
 
using namespace std;
int main ()
{  
    int num, i, count = 0;
    cout << "Enter the number to be checked : ";
    cin >> num;
    if (num == 0)
    {
        cout << "\n" << num << " is not prime";
        exit(1);
    }
    else   {
            for(i=2; i < num; i++)
                if (num % i == 0)
                    count++;
    }
    if (count > 1)
 	    cout << "\n" << num << " is not prime.";
    else
        cout << "\n" << num << " is prime.";
    return 0;
}

1. The user is asked to enter the number to be checked and stored in the variable ‘num’.
2. The variable ‘count’ is initialized as 0.
3. If num is 0, it is not a prime number.
4. The result is printed and program is exited.
5. Else, using a for loop starting from 2, num is checked if it is divisible by any natural number.
6. If it is divisible, count is incremented.
7. The loop is exited when the condition is not true.
8. If count is greater then 1, it is not a prime number, else it is a prime number.
9. The result is then printed.

Time Complexity: O(N)
The time complexity of the given code is O(N), where N is the input number num. This is because the code uses a loop that iterates from 2 to num – 1 to check for divisors.

Space Complexity: O(1)
The space complexity of the code is O(1), constant space. It uses a fixed number of variables that do not depend on the input size, so the space used remains constant.

Testcase 1: In this case, we enter the number “5” as input to check whether it is a prime number or not.

Enter the number to be checked : 5
5 is prime.

Testcase 2: In this case, we enter the number “0” as input to check whether it is a prime number or not.

Enter the number to be checked : 0
0 is not prime.

Testcase 3: In this case, we enter the number “28” as input to check whether it is a prime number or not.

Enter the number to be checked : 28
28 is not prime.

In this method, we use the “Naive Approach” to determine prime numbers. The Naive Approach includes iterating from 2 up to the square root of the number and checking if the number is divisible by any of these smaller numbers.

Here is the source code of C++ Program to Check if a Number is Prime using naive approach. The program output is shown below.

/*
 * C++ Program to Check Prime Numbers using Naive Approach
 */
 
#include <iostream>
#include <cmath>
 
int main()
{
    int num;
    std::cout << "Enter the number to be checked: ";
    std::cin >> num;
    if (num <= 1)
    {
        std::cout << "\n" << num << " is not prime";
        return 0;
    }
    bool isPrime = true;
    for (int i = 2; i <= sqrt(num); ++i)
    {
        if (num % i == 0)
        {
            isPrime = false;
            break;
        }
    }
    if (isPrime)
        std::cout << "\n" << num << " is prime.";
    else
        std::cout << "\n" << num << " is not prime.";
    return 0;
}

1. It prompts the user to input a number to be checked.
2. If the number is less than or equal to 1, it’s not prime, and the program exits.
3. The program uses a loop to iterate from 2 up to the square root of the number.
4. Inside the loop, it checks if the number is divisible by any of these smaller numbers.
5. If a divisor is found, it’s not prime; otherwise, it’s prime.
6. The result is displayed to the user.

Time Complexity: O(sqrt(N))
The program’s time complexity is O(sqrt(N)), where N is the input number, due to the loop iterating up to the square root of N for prime checking.

Space Complexity: O(1)
The space complexity is O(1), as the program uses only a few variables with constant memory usage regardless of the input size.

Testcase 1: In this case, we enter the number “23” as input to check whether it is a prime number or not.

Enter the number to be checked : 23
23 is prime.

Testcase 2: In this case, we enter the number “15” as input to check whether it is a prime number or not.

Enter the number to be checked : 15
15 is not prime.

To practice programs on every topic in C++, please visit “Programming Examples in C++”, “Data Structures in C++” and “Algorithms in C++”.