A prime number is an integer greater than 1 that has exactly two positive divisors: 1 and itself.
Remember
Prime: 2, 3, 5, 7, 11, 13, 17, 19, ...
Not prime: 1 (neither), 4, 6, 8, 9, 10, 12, ...
Rule:
n > 1 and no divisor in 2 .. floor(√n)
n
Divisors
Prime?
7
1, 7
Yes
9
1, 3, 9
No
2
1, 2
Yes (only even prime)
1
1
No
Approach
How to Check a Prime Number in C++
Four clear steps — then reuse the helper to list primes in a range.
If n ≤ 1, return false.
If n is 2 or 3, return true (optional fast path).
Try divisors from 2 to √n; if any divides n, it is not prime.
If no divisor is found, n is prime.
Method
Idea
Time
Best for
Trial to √n
No divisor in 2..√n
O(√n)
Single check (default)
Range scan
Call isPrime for each value
O(N√N)
Listing primes 1..N
Pseudocode
Pseudocode
function IsPrime(n):
if n <= 1: return false
i = 2
while i * i <= n:
if n % i == 0:
return false
i = i + 1
return true
Reference
Cheat Sheet
Keep these facts handy while writing the program.
Topic
Detail
Definition
n > 1 with only divisors 1 and n
1
Neither prime nor composite
2
Smallest and only even prime
Loop bound
i * i <= n (same as i <= √n)
Composite
Has a factor ≤ √n
Classic checks
7 yes; 9 no; 1 no
Try it
Live Preview
Enter an integer to see trial division up to √n and the prime verdict.
Whole numbers only. Tap a chip or type a value.
Result
n = 17
Check divisors from 2 to floor(√17)=4
No divisor found
17 is prime
Trace
Worked Walkthrough — n = 17
Test every candidate divisor up to √17.
Calculation
√17 ≈ 4.123 → check i = 2, 3, 4
17 % 2 = 1
17 % 3 = 2
17 % 4 = 1
No divisor → 17 is prime
Counterexample n = 15:
√15 ≈ 3.87 → check i = 2, 3
15 % 3 == 0 → not prime
Code
C++ Programs
Start with a reusable isPrime helper. Then print every prime in a small range with the same helper.
Example 1 — isPrime Check
Return true only when no divisor exists from 2 through √n.
C++
#include <iostream>
using namespace std;
bool isPrime(int n)
{
if (n <= 1)
{
return false;
}
for (long long i = 2; i * i <= n; i++)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
int main()
{
int number = 17;
cout << number
<< (isPrime(number) ? " is prime" : " is not prime")
<< endl;
return 0;
}
Output
17 is prime
How It Works
n <= 1 is rejected — primes start at 2.
The loop runs while i * i <= n, which means i ≤ √n.
Use long long for i so i * i does not overflow for larger n.
If any i divides n, a third divisor exists → not prime.
For 17, checks stop at 4 and none divide, so the answer is true.
Example 2 — Primes in a Range
Reuse isPrime to print every prime from 1 to 20.
C++
#include <iostream>
using namespace std;
bool isPrime(int n)
{
if (n <= 1)
{
return false;
}
for (long long i = 2; i * i <= n; i++)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
int main()
{
int start = 1;
int end = 20;
cout << "Primes from " << start << " to " << end << ":" << endl;
for (int i = start; i <= end; i++)
{
if (isPrime(i))
{
cout << i << " ";
}
}
cout << endl;
return 0;
}
Output
Primes from 1 to 20:
2 3 5 7 11 13 17 19
How It Works
Same isPrime helper as Example 1 keeps the logic in one place.
The outer loop visits every integer from start to end.
Only values that pass isPrime are printed.
1 is skipped automatically by the helper.
For larger ranges, a sieve is faster — but this pattern is perfect for beginners.
Edge Cases & Pitfalls
Check these before calling the solution done.
1
Not prime
Return false for n ≤ 1 before looping.
2
Even but prime
Do not reject all even numbers — 2 is prime.
Bound
Use i * i ≤ n
Avoid floating sqrt in the loop condition when possible.
Negatives
Not prime here
This tutorial defines primes on positive integers only.
Analysis
Time and Space Complexity
Program
Time
Extra space
isPrime (√n trial)
O(√n)
O(1)
Primes in range 1..N
O(N√N)
O(1)
For large ranges, the Sieve of Eratosthenes is faster. For one number or a short range, √n trial division is enough.
Remember
Key Takeaways
Definition:n > 1 with only divisors 1 and n.
Check: no divisor from 2 to √n.
Facts: 1 is not prime; 2 is the only even prime.
Test set: 17 → yes; 15 → no; 1 → no; 2 → yes.
One line: if n > 1 and nothing from 2 to √n divides it, n is prime.
Frequently Asked Questions
A prime number is an integer greater than 1 with exactly two positive divisors: 1 and itself. Examples: 2, 3, 5, 7, 11.
No. 1 has only one positive divisor, so it is neither prime nor composite.
If n has a factor larger than √n, the matching factor is already smaller than √n and would have been found earlier.
Yes. 2 is the only even prime.
A single isPrime check with trial division up to √n is O(√n). Listing primes from 1 to N by calling isPrime on each value is about O(N√N).
