How to Check for Prime Numbers in Python

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Checking for primality is a fundamental operation in computer science, used heavily in cryptography, hashing, and numerical algorithms.

This guide explores how to check for prime numbers in Python, ranging from simple trial division for small numbers to the Sieve of Eratosthenes for ranges, and the Miller-Rabin test for large numbers.

Basic Primality Testing (Trial Division)

The most straightforward way to check if a number n is prime is to divide it by every integer from 2 up to sqrt(n). If any division has a remainder of 0, the number is composite (not prime).

Why Square Root?

We only need to check up to the square root of n because if n = a * b, then one of the factors (a or b) must be less than or equal to sqrt(n).

import math

def is_prime_basic(n):
    if n < 2:
        return False
    
    limit = int(math.sqrt(n)) + 1
    
    for i in range(2, limit):
        if n % i == 0:
            return False
            
    return True

print(f"Is 7 prime? {is_prime_basic(7)}")
print(f"Is 10 prime? {is_prime_basic(10)}")
print(f"Is 25 prime? {is_prime_basic(25)}")

Output:

Is 7 prime? True
Is 10 prime? False
Is 25 prime? False

Optimized Primality Testing (6k ± 1 Rule)

We can optimize the trial division further.

1. Check divisibility by 2 and 3 explicitly.
2. If not divisible, we can skip all even numbers and all multiples of 3 in our loop.
3. All primes greater than 3 are of the form 6k ± 1. This allows us to increment our loop by 6, checking only i and i+2.

def is_prime_optimized(n):
    if n < 2: return False
    if n == 2 or 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

print(f"Is 97 prime? {is_prime_optimized(97)}")
print(f"Is 1000000007 prime? {is_prime_optimized(1000000007)}")

Output:

Is 97 prime? True
Is 1000000007 prime? True

Generating a Range of Primes (Sieve of Eratosthenes)

If you need to find all prime numbers up to a specific limit (e.g., all primes under 1 million), checking them one by one is inefficient. The Sieve of Eratosthenes is the standard algorithm for this.

It works by marking the multiples of each prime starting from 2.

def sieve_of_eratosthenes(limit):
    primes = [True] * (limit + 1)
    primes[0] = primes[1] = False # 0 and 1 are not primes

    for i in range(2, int(limit**0.5) + 1):
        if primes[i]:
            for j in range(i*i, limit + 1, i):
                primes[j] = False

    return [num for num, is_prime in enumerate(primes) if is_prime]

print(f"Primes up to 50: {sieve_of_eratosthenes(50)}")

Output:

Primes up to 50: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Advanced: Probabilistic Testing (Miller-Rabin)

For extremely large numbers (like those used in cryptography with hundreds of digits), trial division is too slow. The Miller-Rabin test is a probabilistic algorithm: it returns "Composite" (definitely not prime) or "Probably Prime".

By running the test multiple times (k), the probability of error becomes infinitesimally small.

import random

def miller_rabin(n, k=5):
    if n <= 1 or n == 4: return False
    if n <= 3: return True
    
    d = n - 1
    r = 0
    while d % 2 == 0:
        d //= 2
        r += 1

    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n) # Efficient modular exponentiation: (a^d) % n
        
        if x == 1 or x == n - 1:
            continue
            
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
            
    return True

large_prime = 8191 
print(f"Is {large_prime} prime? {miller_rabin(large_prime)}")

Output:

Is 8191 prime? True

Conclusion

Choosing the right primality test depends on your specific use case:

1. Single Number (Small/Medium): Use Optimized Trial Division (Method 2). It is simple and deterministic.
2. Ranges of Numbers: Use the Sieve of Eratosthenes (Method 3). It is the fastest way to generate lists of primes.
3. Massive Numbers: Use Miller-Rabin (Method 4). It is necessary for cryptography-grade numbers where O(sqrt(n)) is computationally impossible.