Beginner Python Exercises

Check a Prime Number in Python

Is 29 prime? Test divisors only up to the square root and get the answer quickly.

  • Beginner
  • 2 min read
  • 1 runnable example
What you'll learn
  • The definition of a prime number
  • Looping over possible divisors
  • Stopping once divisor * divisor > number
Is 29 prime? Try divisors while d * d <= 29
229 % 2 = 1
329 % 3 = 2
429 % 4 = 1
529 % 5 = 4
No divisor found, so 29 is prime.

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.

From tile rectangles to code
number > 1🚪 Only numbers above 1 can be prime
divisor * divisor <= number🪞 Stop at the square: later rectangles are repeats
number % divisor == 0🔍 A full rectangle fits: not prime
divisor += 1➡️ Try the next width
If no divisor is found up to the square root, the number is prime.
In one sentence

A prime number is a whole number greater than 1 whose only positive divisors are 1 and itself.

Key points

  1. is_prime = number > 1 starts with False for 0, 1 and negative numbers, which are never prime.
  2. while divisor * divisor <= number and is_prime: stops at the square root or as soon as a divisor is found.
  3. number % divisor == 0 means divisor divides the number exactly.
  4. 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

Run code →
main.py
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}")
Get a Run button for this example

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.

  1. Change the input and predict the output before running.
  2. Handle empty or invalid input.
  3. Wrap the logic in a function and add more test cases.
Run in the Python compiler →

Common mistakes

Treating 1 as a prime

1 has only one divisor, so it is not prime. Check number > 1 first.

Problem
is_prime = True  # 1 would be reported as prime
Fix
is_prime = number > 1

Looping all the way to the number

It gives the right answer but tries far more divisors than needed.

Problem
for divisor in range(2, number):
Fix
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.

All challenges