# C++ Program to Check Prime Number

Problem Description

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

What is Prime Number?

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.

Problem Solution

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.

Method 1: C++ Program to Check Prime Numbers

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

C++ Program/Source code

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;
}```
Program Explanation

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.

Runtime Test Cases

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

Method 2: Prime Number Program in C++ using Loops (Naive Approach)

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.

Program/Source code

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;
}```
Program Explanation

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.

Runtime Test Cases

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