17 Prime
- Check idea
- No divisor from
2tosqrt(17)divides 17.
Check Prime Number in Python
What you’ll learn
- A clear idea of prime versus composite, and why 1 is a special case.
- How trial division works and why checking only up to √n is enough.
- Two complete Python programs: check one number and print primes in a range, plus a browser live preview.
Overview
You will answer one question: “Is this integer n prime?” We try possible factors. If no factor divides n, the number is prime. Then we reuse the same function to print all primes in a range.
Two programs
Example 1 checks one value (like 17). Example 2 lists primes from 1 to 20.
Live preview
Type a number and instantly see prime/not-prime with the first divisor when not prime.
Interview-ready details
Includes edge cases (n ≤ 1, 2), square-root bound, and complexity.
Prerequisites
You only need basics: integer math, loops, and functions.
- Python basics:
def,if,for, andprint(). - Remainder operator
%and square root viai * i <= nloop condition.
What is a prime number?
A prime number is an integer greater than 1 with only two positive divisors: 1 and itself.
If any integer between 2 and n-1 divides n exactly, then n is composite (not prime).
Prime exactly two divisors: 1 and n
Composite has extra divisors
Special case 1 is neither
Why checking to sqrt(n) is enough
If n is composite, then n = a * b for integers a, b > 1. At least one of them must be ≤ sqrt(n). So a divisor will appear by the time you test up to i * i <= n.
Example: n = 15
15 = 3 * 5. Since 3 ≤ sqrt(15), the loop catches divisor 3 and declares 15 as not prime.
Quick examples
18 Not prime
- Factor
18 % 2 == 0so 18 is composite.
Takeaway: one factor is enough to prove “not prime”. To prove prime, no factors must exist up to sqrt(n).
Live preview
This browser demo follows the same algorithm as the Python function: handle small values, then test divisors while i * i <= n.
- Enter an integer (try 17, 1, or 18).
- Click Run check or press Enter.
- Read the verdict and reason.
Algorithm
Goal: return True when n is prime, otherwise return False.
Handle small values
If n <= 1, it is not prime.
Try divisors
Loop i from 2 while i * i <= n. If n % i == 0, then not prime.
Finish
If no divisor is found, return prime.
List primes in a range
For each number in [start, end], call is_prime() and print only True cases.
📜 Pseudocode
Pseudocode
function isPrime(n):
if n < 2:
return false
for i from 2 while i * i <= n:
if n mod i = 0:
return false
return true1
Check a single number
This Python function handles n <= 1, then checks divisors only up to sqrt(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
test_number = 17
if is_prime(test_number):
print(f"{test_number} is a prime number.")
else:
print(f"{test_number} is not a prime number.")2
Prime numbers between 1 and 20
Reuse is_prime() and print primes in a small interval.
python
def is_prime(num: int) -> bool:
if num <= 1:
return False
i = 2
while i * i <= num:
if num % i == 0:
return False
i += 1
return True
start, end = 1, 20
print(f"Prime numbers in the range {start} to {end}:")
for value in range(start, end + 1):
if is_prime(value):
print(value, end=" ")
print()Optimization and style notes
Skip evens. Handle 2 first, then test only odd divisors for faster checks.
Many numbers? For lots of primes up to N, use a sieve. Trial division is best for simple one-off checks.
Interview line: “Guard n < 2, then trial divide up to sqrt(n), so time is O(sqrt(n)).”
❓ FAQ
A prime is a whole number bigger than 1 that cannot be split into two smaller whole factors (except 1 times itself). Its only positive divisors are 1 and the number itself.
No. By the usual definition, primes start at 2. The number 1 has only one positive divisor, so it is neither prime nor composite.
Yes. It is the smallest and the only even prime.
If n = a*b and both a and b were larger than sqrt(n), then a*b would be larger than n. So any non-trivial factor must appear at or below sqrt(n).
Not for huge values, but it is the standard beginner and interview approach for single-number checks.
Primality is defined for integers greater than 1, so negatives are treated as not prime.
🔄 Input / output examples
Change test_number in Example 1 or use input() for interactive checks.
| Input n | Typical output |
|---|---|
| 17 | 17 is a prime number. |
| 18 | 18 is not a prime number. |
| 2 | 2 is a prime number. |
| 1 | 1 is not a prime number. |
Edge cases and pitfalls
n = 2
Smallest prime
2 is prime and must return True.
n <= 1
Not prime
Always handle this case first to avoid wrong output.
Perfect squares
Watch boundary
Use i * i <= n (not <) so values like 9 detect factor 3.
⏱️ Time and space complexity
| Method | Time | Extra space |
|---|---|---|
| Trial to n/2 | O(n) | O(1) |
| Trial to sqrt(n) | O(sqrt(n)) | O(1) |
| Range check [a, b] | About O((b-a)*sqrt(b)) | O(1) |
Summary
- Prime means
n > 1and no divisors other than 1 and n. - Trial division up to
sqrt(n)is the key optimization. - Always handle
n <= 1correctly in both single and range checks.
Did you know?
The only even prime is 2. Every integer greater than 1 is either prime or composite—except 1, which is neither. There are infinitely many primes.
About the author
9 people found this page helpful