Prime Check in C++

Prime check in C++: test divisors up to sqrt(n). 1 is not prime. 2 is.

BeginnerLoop ProgramsExample 8 of 14

prime-check.cpp

1#include <iostream>
2#include <cmath>
3using namespace std;
4
5int main() {
6    int num;
7    bool isPrime = true;
8    
9    cout << "Enter a number: ";
10    cin >> num;
11    
12    if (num <= 1) {
13        isPrime = false;
14    } else {
15        for (int i = 2; i <= sqrt(num); i++) {
16            if (num % i == 0) {
17                isPrime = false;
18                break;
19            }
20        }
21    }
22    
23    if (isPrime) {
24        cout << num << " is a prime number" << endl;
25    } else {
26        cout << num << " is not a prime number" << endl;
27    }
28    
29    return 0;
30}

Output

Enter a number: 17
17 is a prime number

What's going on

A prime number is an integer greater than 1 whose only positive divisors are 1 and itself. 17 is prime. 1 is not. 9 is not (3×3). 2 is the only even prime.

#include <cmath>

For sqrt. The loop only needs to test up to the square root.

int num;

bool isPrime = true;

Assume prime until a divisor shows up. Start false and you'll mark every prime as composite unless you remember to flip it.

cin >> num;

Sample: 17.

if (num <= 1)

isPrime = false;

1 has one divisor. 0 and negatives aren't primes. Don't send them into the loop.

else { for (int i = 2; i <= sqrt(num); i++)

If num % i == 0, you found a factor. Set isPrime = false and break. No point keeping going.

Why sqrt: if n = a × b and a ≤ b, then a ≤ √n. A factor bigger than √n already had a partner you would have seen. Checking through n-1 works and wastes time. 17's loop tests 2, 3, 4 (√17 ≈ 4.1). None divide 17.

Walk 9: √9 is 3. i = 2, 9 % 2 ≠ 0. i = 3, 9 % 3 == 0 → not prime.

Walk 4: i = 2, 4 % 2 == 0 immediately.

Walk 2: sqrt(2) ≈ 1.41, so i <= 1.41 never runs with i starting at 2. isPrime stays true. Correct.

Then print " is a prime number" or " is not". Sample: 17 is a prime number.

Even numbers after 2 are never prime. You could skip them after testing 2. This program doesn't; sqrt already keeps it cheap for homework sizes.

PreviousPalindrome Check NextPrimes in Range