Python programs / Numbers / Prime number check

Python Program to Check a Prime Number

Beginner Numbers

Checks whether a number is prime by trying every divisor from 2 up to its square root.

A prime number is a whole number greater than 1 that only 1 and itself divide exactly. 13 is prime; 15 isn't, as 3 × 5 = 15. To check a number, the program tries dividing it by 2, 3, 4 and so on, but only up to its square root: for 97 that's 2 to 9, eight divisions instead of 95.

Program

def is_prime(number):
    """True if number is a prime number."""
    if number < 2:
        return False
    divisor = 2
    while divisor * divisor <= number:
        if number % divisor == 0:
            return False
        divisor += 1
    return True


print("29:", is_prime(29))
print("91:", is_prime(91))

Open in the editor Download prime_check.py

Output

29: True
91: False

How it works

  1. Numbers below 2 (1, 0 and the negatives) aren't prime, so the function says no straight away.
  2. divisor is the first number to try: 2.
  3. The loop goes on while divisor * divisor <= number, that is, while the divisor is at most the square root of the number. Divisors come in pairs that multiply to the number: 91 = 7 × 13, and √91 is about 9.5. A divisor above the square root has its partner below it, and the loop has already found that one.
  4. If the divisor goes into the number exactly, the number isn't prime, and the function stops without trying the rest.
  5. Otherwise it moves on to the next divisor.
  6. The loop ended without finding a divisor, so the number is prime.
  7. The program checks 29, which is prime, and 91, which looks prime but is 7 × 13.

For 29 the loop tries 2, 3, 4 and 5, then stops, as 6 × 6 = 36 is more than 29. For 91 it finds 7 on its sixth try.

Other ways to write it

With a for loop and math.isqrt()

math.isqrt() gives the whole-number part of a square root (math.isqrt(97) is 9), so a for loop over range() can count the divisors.

import math

def is_prime(number):
    if number < 2:
        return False
    for divisor in range(2, math.isqrt(number) + 1):
        if number % divisor == 0:
            return False
    return True

print(is_prime(97), is_prime(100))

Trying only odd divisors

Once 2 is ruled out the number is odd, and no even number divides an odd one, so the loop can start at 3 and go up in steps of 2. That halves the work.

def is_prime(number):
    if number < 2:
        return False
    if number % 2 == 0:
        return number == 2
    divisor = 3
    while divisor * divisor <= number:
        if number % divisor == 0:
            return False
        divisor += 2
    return True

print(is_prime(2), is_prime(7919), is_prime(7921))

Try it yourself

  • Check 1, 2 and 97. 1 isn't prime, and 2 is the only even prime.
  • Check 7921, which is 89 × 89. Change <= to < in the while line and it wrongly says True, as the loop stops before 89. Then change it back.
  • Count how many times the loop runs for 1,000,003, which is prime: 999 times. Without the square root limit, it would be 1,000,001.
  • Change the function to return the smallest divisor it finds, or the number itself when it's prime, so 91 gives 7.

More numbers programs

Share this program