Home / Python / Example programs / Loops and numbers

Python program: Check whether a number is prime

A prime has exactly two divisors: 1 and itself.

The code

def is_prime(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:          # only test up to the square root
        if n % d == 0:
            return False
        d += 1
    return True

for n in [1, 2, 9, 17, 97, 100]:
    print(n, is_prime(n))

Output

1 False
2 True
9 False
17 True
97 True
100 False

How it works

If n has a divisor bigger than its square root, it also has one smaller, so testing up to √n is enough. That makes the check far faster for big numbers.

Learn the ideas behind it in the free lesson Loops.