Prime Check
Program to check if a number is prime
C++ Prime Check Program
This program helps you to learn the fundamental structure and syntax of C++ programming.
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int num;
bool isPrime = true;
cout << "Enter a number: ";
cin >> num;
if (num <= 1) {
isPrime = false;
} else {
for (int i = 2; i <= sqrt(num); i++) {
if (num % i == 0) {
isPrime = false;
break;
}
}
}
if (isPrime) {
cout << num << " is a prime number" << endl;
} else {
cout << num << " is not a prime number" << endl;
}
return 0;
}Enter a number: 17 17 is a prime number
Understanding Prime Check
This program checks whether a given number is prime. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. This program demonstrates efficient prime checking using the square root optimization, which is a fundamental algorithm in number theory and computer science.
---
1. What is a Prime Number?
A prime number is a natural number greater than 1 that:
Examples of prime numbers:
-
2
(smallest prime, only even prime)
-
3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...
Examples of non-prime (composite) numbers:
-
4
(divisible by 1, 2, 4)
-
6
(divisible by 1, 2, 3, 6)
-
8
(divisible by 1, 2, 4, 8)
-
9
(divisible by 1, 3, 9)
-
1
(not prime, only one divisor)
Special cases:
-
1
is NOT prime (only one divisor)
-
2
is the only even prime number
Applications:
---
2. Header Files Used
#include <iostream>
cout for output and cin for input#include <cmath>
sqrt() function---
3. Declaring Variables
int num;
bool isPrime = true;
Variable `num`:
Variable `isPrime`:
-
Initialized to `true`
false if we find a divisorWhy initialize to `true`?
falsetrue---
4. Taking Input From User
cin >> num;
Example:
17
num = 17---
5. Checking Edge Cases
if (num <= 1)
isPrime = false;
Why check for num <= 1?
-
1
has only one divisor (itself)
-
0 and negative numbers
are not prime
What happens:
num <= 1, set isPrime = falseExamples:
num = 1 → isPrime = false ✅num = 0 → isPrime = false ✅num = -5 → isPrime = false ✅---
6. The Square Root Optimization
for (int i = 2; i <= sqrt(num); i++)
Why only check up to √n?
Key mathematical insight:
Efficiency comparison:
Naive approach (checking 2 to n-1):
Optimized approach (checking up to √n):
-
Much faster!
---
7. Checking for Divisors
if (num % i == 0)
isPrime = false;
break;
What this does:
i divides num evenly (no remainder)num % i == 0, then i is a divisorisPrime = falsebreak; exits loop immediately (no need to check further)Why use `break;`?
---
8. Step-by-Step Example
Example 1: Checking if 17 is prime
Step 1: Edge case check
17 <= 1 →false
→ continue
Step 2: Loop through potential divisors
Iteration 1 (i = 2):
17 % 2 == 0 → 1 == 0 →false
Iteration 2 (i = 3):
17 % 3 == 0 → 2 == 0 →false
Iteration 3 (i = 4):
17 % 4 == 0 → 1 == 0 →false
Step 3: Result
isPrime remains true-
17 is prime
✅
Example 2: Checking if 15 is prime
Step 1: Edge case check
15 <= 1 →false
→ continue
Step 2: Loop
Iteration 1 (i = 2):
15 % 2 == 0 → 1 == 0 →false
Iteration 2 (i = 3):
15 % 3 == 0 → 0 == 0 →true
✅
isPrime = falsebreak; → exit loopStep 3: Result
isPrime = false-
15 is not prime
❌
---
9. Visual Representation
Checking 17 (Prime):
Check divisors from 2 to √17 (≈4.12):
No divisors found → Prime ✅
Checking 15 (Composite):
Check divisors from 2 to √15 (≈3.87):
Divisor found → Not prime ❌
---
10. Why This Algorithm is Efficient
For large numbers:
-
100x faster!
Time complexity:
---
11. Displaying the Result
If prime:
cout << num << " is a prime number" << endl;
If not prime:
cout << num << " is not a prime number" << endl;
Examples:
"17 is a prime number"
"15 is not a prime number"
---
12. Special Cases
Case 1: Number 2
isPrime remains true ✅Case 2: Even numbers > 2
isPrime = false ✅Case 3: Perfect squares
---
Summary
break; to exit early when divisor is foundThis program teaches:
break;)Understanding prime checking helps in:
Prime numbers are fundamental in mathematics and computer science, and this efficient checking algorithm is used in many applications, from cryptography to number theory research.
Let us now understand every line and the components of the above program.
Note: To write and run C++ programs, you need to set up the local environment on your computer. Refer to the complete article Setting up C++ Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your C++ programs.
Practical Learning Notes for Prime Check
This C++ program is part of the "Loop Programs" topic and is designed to help you build real problem-solving confidence, not just memorize syntax. Start by understanding the goal of the program in plain language, then trace the logic line by line with a custom input of your own. Once you can predict the output before running the code, your understanding becomes much stronger.
A reliable practice pattern is to run the original version first, then modify only one condition or variable at a time. Observe how that single change affects control flow and output. This deliberate style helps you understand loops, conditions, and data movement much faster than copying full solutions repeatedly.
For interview preparation, explain this solution in three layers: the high-level approach, the step-by-step execution, and the time-space tradeoff. If you can teach these three layers clearly, you are ready to solve close variations of this problem under time pressure.