Home / C++ / Loop / Recursion / C++ Program to Check If a Number Is a Prime or Not

C++ Program to Check If a Number Is a Prime or Not

in , ,
Prime number

C++ program to check if a number is a prime or not has been shown here. A positive number $n$ is called a prime, if it does not have any divisor except $1$ and $n$. For example if $n = 13$, it is prime but if $n = 10$, it is not prime as $10$ is divisible by $2$ and $5$ apart from $1$ and $10$. The algorithm, pseudocode and time complexity of the program have been shown below.






1. Algorithm to check if a number is a prime or not


1. Take a positive number n as input.

2. Check for each i $\in$ [2, $\sqrt{n}$], if n is divisible by i

3. If step 2 is true for atleast one i, then n is not a prime.

4. If step 2 is false for each i, then n is a prime.




2. Pseudocode to check if a number is a prime or not


Input : A postive number $n$

Output : $n$ is a prime or not a prime

1. Procedure checkPrime($n$):

2. $flag \leftarrow 0$

3. Repeat for $i \in [2, \sqrt{n}]$:

4. If $n \mod i$ = 0:

5. $flag \leftarrow 1$

6. break

7. If $n = 1$

8. Return "not a prime"

9. Else:

10. If $flag = 1$:

11. Return "not a prime"

12. Else:

13. Return "a prime"

14. End Procedure





3. Time complexity to check if a number is a prime or not


Time Complexity: O($\sqrt{n}$)

Where n is the input number.





4. C++ Program & output to check if a number is a prime or not using iteration

Code has been copied
/*********************************
    	alphabetacoder.com
C++ program to check if a number 
is a prime or not using iteration
***********************************/

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    // declare variables
    int n, i, flag = 0;

    // take input of the number
    cout << "Enter the number = ";
    cin >> n;

    //check if n is a prime or not
    //If n has divisor between 2 and
    // square root of n, then 
    // n is not prime else n is prime
    for (i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            flag = 1; // mark as not prime
            break; // exit from loop
        }
    }

    // dispay the result
    if (n == 0 || n == 1)
        cout << n << " is neither a prime nor a composite!" << endl;
    else {
        if (flag == 0)
            cout << n << " is a prime!" << endl;
        else
            cout << n << " is not a prime!" << endl;
    }

    return 0;
}

Output

Case 1:

Enter the number = 30

30 is not a prime!


Case 2:

Enter the number = 1

1 is neither a prime nor a composite!


Case 3:

Enter the number = 11

11 is a prime!





5. C++ Program & output to check if a number is a prime or not using recursion

Code has been copied
/*********************************
	 alphabetacoder.com
C++ program to check if a number 
is a prime or not using recursion
***********************************/

#include <iostream>
#include <cmath>

using namespace std;

// recursive function to check 
// if a number is prime or not
// check divisor upto sqrt(num)
int check_prime(int num, int i) {
    // return 1, as num is prime
    if (i > sqrt(num))
        return 1;
    // return 0, as num is not prime
    if (num % i == 0)
        return 0;
    // call function
    return check_prime(num, i + 1);
}

int main() {
    // declare variables
    int n;

    // take input of the number
    cout << "Enter the number = ";
    cin >> n;

    //check if n is a prime or not
    // by calling the function
    // if the function returns 1, 
    // it is considered prime else
    // it is considered not prime
    if (n == 0 || n == 1)
        cout << n << " is neither a prime nor a composite!" << endl;
    else {
        if (check_prime(n, 2))
            cout << n << " is a prime!" << endl;
        else
            cout << n << " is not a prime!" << endl;
    }

    return 0;
}

Output

Case 1:

Enter the number = 127

127 is a prime!


Case 2:

Enter the number = 0

0 is neither a prime nor a composite!


Case 3:

Enter the number = 231

231 is not a prime!





Labels: , ,