Skip to main content

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):
    # 1. Handle edge cases
    if n < 2:
        return False
    
    # 2. Check divisibility from 2 to sqrt(n)
    # We add 1 to include the square root itself in the range
    limit = int(math.sqrt(n)) + 1
    
    for i in range(2, limit):
        if n % i == 0:
            return False
            
    return True

# Testing
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):
    # 1. Handle small numbers and even numbers
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n % 2 == 0 or n % 3 == 0: return False

    # 2. Check using 6k +/- 1 optimization
    i = 5
    while i * i <= n:
        # Check i and i+2 (e.g., 5 and 7, 11 and 13)
        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
tip

Use this optimized method for general-purpose primality checking of individual numbers up to roughly 10^{12}.

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):
    # Initialize a list of Booleans (True means potentially prime)
    # Indices represent numbers 0 to limit
    primes = [True] * (limit + 1)
    primes[0] = primes[1] = False # 0 and 1 are not primes

    # Iterate from 2 to sqrt(limit)
    for i in range(2, int(limit**0.5) + 1):
        if primes[i]:
            # Mark all multiples of i as False (starting from i*i)
            for j in range(i*i, limit + 1, i):
                primes[j] = False

    # Collect numbers that remained True
    return [num for num, is_prime in enumerate(primes) if is_prime]

# Get all primes up to 50
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):
    # Handle base cases
    if n <= 1 or n == 4: return False
    if n <= 3: return True
    
    # Find d such that n-1 = d * 2^r
    d = n - 1
    r = 0
    while d % 2 == 0:
        d //= 2
        r += 1

    # Perform k rounds of testing
    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:
            # If loop didn't break, it's composite
            return False
            
    return True

# Test a large known prime (Mersenne prime M13)
large_prime = 8191 
print(f"Is {large_prime} prime? {miller_rabin(large_prime)}")

Output:

Is 8191 prime? True
note

The pow(base, exp, mod) function in Python is highly optimized for modular exponentiation, which is the core of the Miller-Rabin efficiency.

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.

Table of Contents