Check a Prime Number in Python
Is 29 prime? Test divisors only up to the square root and get the answer quickly.
- The definition of a prime number
- Looping over possible divisors
- Stopping once divisor * divisor > number
Only test up to √n
The problem
Prime numbers are behind encryption on the internet, hash tables and many puzzles. Checking whether a number is prime by trying every divisor up to the number itself works for 29, but becomes painfully slow for large numbers. A small insight makes the check much faster.
Think of it like this
Checking for divisors is like trying to lay tiles in a full rectangle. 36 tiles fit as 1×36, 2×18, 3×12, 4×9 and 6×6. After the square (6×6) the same rectangles come back turned around, so there is nothing new to find beyond the square root. 29 tiles only fit as 1×29, so 29 is prime.
number > 1🚪 Only numbers above 1 can be primedivisor * divisor <= number🪞 Stop at the square: later rectangles are repeatsnumber % divisor == 0🔍 A full rectangle fits: not primedivisor += 1➡️ Try the next widthA prime number is a whole number greater than 1 whose only positive divisors are 1 and itself.
Key points
is_prime = number > 1starts with False for 0, 1 and negative numbers, which are never prime.while divisor * divisor <= number and is_prime:stops at the square root or as soon as a divisor is found.number % divisor == 0meansdivisordivides the number exactly.- For 29 the loop only tries 2, 3, 4 and 5 before it can say the number is prime.
When should you use it?
- Number puzzles and exercises such as listing primes or finding prime factors.
- Learning why stopping early and checking only up to a limit make loops faster.
- Validating input in maths tools.
When not to use it
- Listing all primes up to a large limit: the Sieve of Eratosthenes is much faster than checking each number.
- Cryptography with numbers hundreds of digits long: real systems use probabilistic tests.
Example code
number = 29
is_prime = number > 1
divisor = 2
while divisor * divisor <= number and is_prime:
if number % divisor == 0:
is_prime = False
divisor += 1
print(f"{number} is prime: {is_prime}")
Result of running the code
29 is prime: True
Code explanation
is_prime starts as number > 1, so 0, 1 and negative numbers are rejected before the loop. The loop tries divisors from 2 upward and stops in two cases: when divisor * divisor is larger than the number, because any larger factor would pair with a smaller one already tried, or when a divisor has been found. For 29 none of 2, 3, 4 or 5 divides it, so is_prime stays True.
Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.
Practice exercises
Modify the runnable example with the exercises below to build understanding beyond copying the result.
- Change the input and predict the output before running.
- Handle empty or invalid input.
- Wrap the logic in a function and add more test cases.
Common mistakes
Treating 1 as a prime
1 has only one divisor, so it is not prime. Check number > 1 first.
is_prime = True # 1 would be reported as prime
is_prime = number > 1
Looping all the way to the number
It gives the right answer but tries far more divisors than needed.
for divisor in range(2, number):
while divisor * divisor <= number:
Finished this lesson?
Mark it as learned to track your progress.
Practice with a challenge
Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.
- Prime Number Check Decide whether a number is prime. Easy
- Largest Prime Factor Find the largest prime that divides a positive integer. Medium
- List Primes With a Sieve Find primes up to a limit by marking composite multiples. Medium