C++ Program to Check Prime Number

A C++ program to check if a number is prime uses a loop to test divisibility from 2 up to the square root of the number with code like for (int i = 2; i * i <= n; i++) and returns prime if no divisor is found.

Examples

Input7

Output7 is a prime number.

Input10

Output10 is not a prime number.

Input2

Output2 is a prime number.

How to Think About It

To check if a number is prime, think about whether it can be divided evenly by any number other than 1 and itself. You only need to check divisors up to the square root of the number because if a larger factor exists, a smaller one must also exist. If no divisor is found, the number is prime.

Algorithm

1

Get the input number.

2

If the number is less than 2, it is not prime.

3

Check divisibility from 2 up to the square root of the number.

4

If any divisor divides the number evenly, it is not prime.

5

If no divisors are found, the number is prime.

6

Print the result.

Code

cpp

#include <iostream>
#include <cmath>

int main() {
    int n;
    std::cout << "Enter a number: ";
    std::cin >> n;

    if (n < 2) {
        std::cout << n << " is not a prime number." << std::endl;
        return 0;
    }

    bool isPrime = true;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            isPrime = false;
            break;
        }
    }

    if (isPrime)
        std::cout << n << " is a prime number." << std::endl;
    else
        std::cout << n << " is not a prime number." << std::endl;

    return 0;
}

Output

Enter a number: 7
7 is a prime number.

Dry Run

Let's trace the input 7 through the code to see how it checks for prime.

1

Input number

User enters n = 7

2

Check if less than 2

7 is not less than 2, continue

3

Loop from 2 to sqrt(7)

Check i=2: 7 % 2 != 0, no divisor found

4

End loop

No divisors found, isPrime remains true

5

Print result

Print '7 is a prime number.'

i	n % i	isPrime
2	1	true

Why This Works

Step 1: Check small numbers

Numbers less than 2 are not prime by definition, so we handle them first.

Step 2: Loop to square root

We only check divisors up to the square root because any factor larger than that pairs with a smaller factor already checked.

Step 3: Determine primality

If no divisor divides the number evenly, the number is prime; otherwise, it is not.

Alternative Approaches

Check divisibility up to n-1

cpp

#include <iostream>

int main() {
    int n;
    std::cout << "Enter a number: ";
    std::cin >> n;

    if (n < 2) {
        std::cout << n << " is not a prime number." << std::endl;
        return 0;
    }

    bool isPrime = true;
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            isPrime = false;
            break;
        }
    }

    if (isPrime)
        std::cout << n << " is a prime number." << std::endl;
    else
        std::cout << n << " is not a prime number." << std::endl;

    return 0;
}

This method is simpler but slower because it checks all numbers up to n-1.

Use a function to check primality

cpp

#include <iostream>
#include <cmath>

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int n;
    std::cout << "Enter a number: ";
    std::cin >> n;

    if (isPrime(n))
        std::cout << n << " is a prime number." << std::endl;
    else
        std::cout << n << " is not a prime number." << std::endl;

    return 0;
}

Using a function improves code reuse and readability.

Complexity: O(√n) time, O(1) space

Time Complexity

The loop runs up to the square root of n, so the time grows roughly with √n.

Space Complexity

Only a few variables are used, so space is constant.

Which Approach is Fastest?

Checking up to √n is faster than checking up to n-1, and using a function helps organize code but does not affect complexity.

Approach	Time	Space	Best For
Check up to √n	O(√n)	O(1)	Efficient primality test
Check up to n-1	O(n)	O(1)	Simple but slower
Function-based check	O(√n)	O(1)	Reusable and clean code