Python Check If Number Is Prime (5 Best Ways)

Problem Formulation

A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. This implies it has only two divisors: 1 and itself.

🎨 Challenge: Create a Python function that will determine if a number given as input is a prime number or not.

Method 0: Library

If you’re allowed to use a Python library, there are several great libraries to check if a number is prime. One of the most popular ones is SymPy, which is a Python library for symbolic mathematics. It includes a function to check for primality.

Here’s how you can use SymPy to check if a number is prime:

First, you need to install SymPy if you haven’t already. You can install it using pip:

pip install sympy

Then, you can use the isprime function from SymPy to check if a number is prime:

from sympy import isprime

# Example usage:
number = 29
print(f"Is {number} a prime number? {isprime(number)}")

The isprime function returns True if the number is prime and False otherwise.

💡 Info: SymPy is very useful for a wide range of mathematical computations beyond just prime checking, including algebra, calculus, discrete mathematics, and quantum physics, among others.

Method 1: Trial Division

The simplest method to check for a prime number is trial division. We check if our number has any divisor other than 1 and itself by testing all integers from 2 to the square root of the number. If no divisors are found, the number is prime.

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

This function first handles the edge case where n is less than or equal to 1. Then it checks for divisors up to the square root of n. If a divisor is found, it returns False; otherwise, it returns True.

Method 2: Sieve of Eratosthenes (For Range Of Numbers)

While not directly a method to check if a single number is prime, the Sieve of Eratosthenes is a classic algorithm for generating a list of primes up to a certain limit. Once the list is generated, we can then check if the number in question is a prime by simply determining if it is in the list.

def is_prime(n):
    if n <= 1:
        return False
    elif n <= 3:
        return True
    elif n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

The sieve_of_eratosthenes function creates a sieve list, marking non-primes as False. In the is_prime function, we utilize the sieve to determine if n is prime.

💡 Explanation: This function first handles simple cases (numbers less than 2 are not prime, 2 and 3 are prime). It then checks divisibility by 2 and 3 to quickly eliminate multiples of these. After that, it iterates over potential divisors starting from 5, checking divisibility by i and i+2 (skipping even numbers and multiples of 3), up to the square root of n. This isn’t the Sieve of Eratosthenes in its classic form but an efficient way to check for a prime number that shares the spirit of eliminating factors by checking divisibility.

If you’re interested in this algorithm, check out my fun one-liner tutorial:

👉 The Sieve of Eratosthenes in Python

Method 3: 6k +/- 1 Optimization

After observing that all primes greater than 3 are of the form 6k ± 1, we can check for divisors in a more optimized way. This avoids checking multiples of 2 and 3.

def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

This code first checks for small numbers (<= 3) and then eliminates numbers divisible by 2 and 3. It then checks for factors of the form 6k ± 1 up to the square root of n.

Method 4: Checking for Primality Using Recursion

Recursion can also be applied to check for a prime number by recursively dividing the number by the current divisor till it either finds a divisor or verifies it’s a prime.

def is_prime_helper(n, divisor):
    if n <= 2:
        return True if n == 2 else False
    if n % divisor == 0:
        return False
    if divisor * divisor > n:
        return True
    return is_prime_helper(n, divisor + 1)

def is_prime(n):
    return is_prime_helper(n, 2)

This code uses a helper function is_prime_helper which determines if a number n is prime by recursively dividing n by a divisor starting from 2.

Method 5: Using the Fermat’s Little Theorem

Fermat’s Little Theorem can sometimes be used as a probabilistic check. According to the theorem, if n is a prime number, then for any integer a, a^n ≡ a (mod n). This can suggest primality, but beware of Fermat liars.

import random

def is_prime(n):
    if n <= 1:
        return False
    for _ in range(5):  # number of trials
        a = random.randint(2, n-1)
        if pow(a, n-1, n) != 1:
            return False
    return True

The code tests the theorem with a random a for a certain number of trials. If the theorem doesn’t hold, n is not prime. If it holds for all tests, n is likely prime.

Bonus One-Liner Method 6: Pythonic Way

For aficionados of Python’s expressive one-liners, here’s a succinct way to check for primality.

is_prime = lambda n: n > 1 and all(n % i for i in range(2, int(n**0.5) + 1))

This lambda function uses all to determine if there are no divisors of n from 2 up to the square root of n.

Check out my new Python book Python One-Liners (Amazon Link).

If you like one-liners, you’ll LOVE the book. It’ll teach you everything there is to know about a single line of Python code. But it’s also an introduction to computer science, data science, machine learning, and algorithms. The universe in a single line of Python!

The book was released in 2020 with the world-class programming book publisher NoStarch Press (San Francisco).

Publisher Link: https://nostarch.com/pythononeliners

Summary/Discussion

While there are multiple methods to check if a number is prime in Python, each comes with its own trade-offs in terms of readability, speed, and accuracy.

• Trial division (Method 1) is the simplest but not the most efficient for large numbers.
• The Sieve of Eratosthenes (Method 2) is great for checking primality within a range, but not optimal for a single large number.
• The 6k +/- 1 optimization (Method 3) improves over trial division for individual numbers.
• Recursion (Method 4) and Fermat’s Little Theorem (Method 5) provide additional ways, with recursion as a fundamental approach, and Fermat’s method serving as a fast, probabilistic test.
• Finally, the Pythonic one-liner (Method 6) showcases the power of Python’s expressive syntax, making it ideal for code golfing and small-scale tests.