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 Python
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 is_prime 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
Python Programs
Start with a reusable is_prime helper. Then print every prime in a small range with the same helper.
Example 1 — is_prime Check
Return True only when no divisor exists from 2 through √n.
python
def is_prime(n: int) -> bool:
if n <= 1:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return True
number = 17
print(f"{number} is prime" if is_prime(number) else f"{number} is not prime")
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.
If any i divides n, a third divisor exists → not prime.
If the loop finishes with no hit, only divisors are 1 and n.
For 17, checks stop at 4 and none divide, so the answer is True.
Example 2 — Primes in a Range
Reuse is_prime to print every prime from 1 to 20.
python
def is_prime(n: int) -> bool:
if n <= 1:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return True
start, end = 1, 20
print(f"Primes from {start} to {end}:")
for i in range(start, end + 1):
if is_prime(i):
print(i, end=" ")
print()
Output
Primes from 1 to 20:
2 3 5 7 11 13 17 19
How It Works
Same is_prime helper as Example 1 keeps the logic in one place.
The outer loop visits every integer from start to end.
Only values that pass is_prime 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 math.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
is_prime (√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 is_prime check with trial division up to √n is O(√n). Listing primes from 1 to N by calling is_prime on each value is about O(N√N).
