How to find prime numbers in Python

Prime numbers form the foundation of modern cryptography and computer science. Python offers efficient ways to identify these unique numbers that are only divisible by 1 and themselves, making it an ideal language for prime number operations.

This guide covers essential techniques for finding prime numbers in Python, with practical examples and optimization tips. All code examples were created with Claude, an AI assistant built by Anthropic.

Checking if a number is prime with a simple function

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

print(is_prime(7), is_prime(10))
True False

The is_prime() function implements a straightforward but foundational approach to prime number detection. It checks each potential divisor from 2 up to one less than the input number, returning False if it finds any number that divides evenly using the modulo operator %.

While this method clearly demonstrates the mathematical concept of prime numbers, it becomes computationally expensive for larger numbers. The function must perform more iterations as the input grows, making it suitable for educational purposes but less ideal for production environments.

  • The function correctly handles edge cases by immediately returning False for numbers less than or equal to 1
  • It uses a simple loop structure that makes the code easy to understand and modify
  • The implementation directly translates the mathematical definition of prime numbers into code

Basic prime number techniques

Building on our basic is_prime() function, we can explore more sophisticated techniques that improve both code readability and computational performance.

Using a for loop with early return for efficiency

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

print(is_prime(17), is_prime(25))
True False

This optimized version of is_prime() significantly reduces the number of divisibility checks needed. The function quickly filters out common non-prime cases by checking divisibility by 2 and 3, then uses a clever mathematical pattern to test remaining potential divisors.

  • Numbers less than or equal to 3 get immediate responses through initial checks
  • The while i * i <= n loop only tests up to the square root of the input number
  • The increment i += 6 works because all prime numbers greater than 3 can be expressed as 6k ± 1

This implementation strikes an excellent balance between code simplicity and computational efficiency. It processes larger numbers much faster than the basic version while remaining readable and maintainable.

Finding all primes up to a limit

def get_primes(limit):
    primes = []
    for num in range(2, limit + 1):
        for i in range(2, num):
            if num % i == 0:
                break
        else:
            primes.append(num)
    return primes

print(get_primes(20))
[2, 3, 5, 7, 11, 13, 17, 19]

The get_primes() function generates a list of all prime numbers up to a specified limit using a straightforward approach. It iterates through each number from 2 to the limit and checks if it's prime by testing potential divisors.

  • The outer loop with range(2, limit + 1) examines each candidate number
  • The inner loop tests divisibility using numbers from 2 up to the candidate
  • Python's else clause after the for loop executes when no divisors are found. This indicates a prime number
  • When a prime is found, the function adds it to the primes list using append()

While this implementation clearly demonstrates the concept, it's not optimized for larger numbers. The function performs more calculations than necessary. However, it serves as an excellent learning tool for understanding prime number generation.

Using list comprehensions for cleaner code

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

primes = [num for num in range(2, 30) if is_prime(num)]
print(primes)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

This implementation combines Python's list comprehension syntax with a concise prime-checking function to create elegant, readable code. The is_prime() function uses the all() built-in function with a generator expression to check divisibility up to the square root of the input number.

  • The n > 1 check efficiently filters out negative numbers and edge cases
  • Using int(n**0.5) calculates the square root without importing the math module
  • The list comprehension [num for num in range(2, 30) if is_prime(num)] creates a list of prime numbers in a single, expressive line

This approach demonstrates how Python's built-in features can produce clean, performant code that remains easy to understand. The combination of list comprehension and generator expression reduces memory usage while maintaining readability.

Advanced prime number algorithms

Building on our list comprehension approach, we can dramatically improve performance with three powerful algorithms that scale efficiently to handle much larger numbers.

Implementing the Sieve of Eratosthenes

def sieve_of_eratosthenes(limit):
    sieve = [True] * (limit + 1)
    sieve[0] = sieve[1] = False
    
    for i in range(2, int(limit**0.5) + 1):
        if sieve[i]:
            for j in range(i*i, limit + 1, i):
                sieve[j] = False
                
    return [i for i, is_prime in enumerate(sieve) if is_prime]

print(sieve_of_eratosthenes(30))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

The Sieve of Eratosthenes algorithm uses a boolean array to efficiently identify prime numbers. It starts by marking all numbers as potentially prime (True), except 0 and 1. The algorithm then systematically eliminates composite numbers by marking their multiples as False.

  • The outer loop only needs to check up to the square root of the limit. This optimization significantly reduces computation time
  • The inner loop starts from i*i because smaller multiples were already marked by previous iterations
  • The final list comprehension with enumerate converts the boolean array into a list of prime numbers

This implementation outperforms our previous approaches for large ranges. The algorithm's efficiency comes from marking composite numbers instead of testing each number individually for primality.

Using the Miller-Rabin primality test

import random

def miller_rabin(n, k=5):
    if n <= 1 or n == 4:
        return False
    if n <= 3:
        return True
        
    d = n - 1
    while d % 2 == 0:
        d //= 2
        
    for _ in range(k):
        if not miller_test(n, d):
            return False
    return True
    
def miller_test(n, d):
    a = 2 + random.randint(1, n - 4)
    x = pow(a, d, n)
    if x == 1 or x == n - 1:
        return True
        
    while d != n - 1:
        x = (x * x) % n
        d *= 2
        if x == 1:
            return False
        if x == n - 1:
            return True
    return False

print([n for n in range(2, 30) if miller_rabin(n)])
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

The Miller-Rabin primality test offers a probabilistic approach to determine if a number is prime. Unlike deterministic methods that check every possible divisor, this algorithm uses random sampling to achieve faster results while maintaining high accuracy.

  • The miller_rabin() function performs initial checks for small numbers and then decomposes n-1 into the form d * 2^r
  • The k parameter controls the number of test rounds. More rounds increase accuracy but require more computation time
  • The miller_test() function implements the core mathematical logic using modular exponentiation with pow() to efficiently handle large numbers

This implementation balances speed and reliability. It works exceptionally well for large numbers where traditional divisibility tests become impractical. The trade-off is a tiny probability of false positives. However, increasing the k value makes such errors extremely unlikely.

Using NumPy for vectorized prime checking

import numpy as np

def prime_sieve_numpy(limit):
    sieve = np.ones(limit + 1, dtype=bool)
    sieve[0:2] = False
    
    for i in range(2, int(np.sqrt(limit)) + 1):
        if sieve[i]:
            sieve[i*i::i] = False
            
    return np.where(sieve)[0]

print(prime_sieve_numpy(30))
[ 2  3  5  7 11 13 17 19 23 29]

NumPy's vectorized operations transform the Sieve of Eratosthenes into a more efficient implementation. The prime_sieve_numpy() function creates a boolean array using np.ones() and marks all numbers as potentially prime. It then systematically eliminates composite numbers through array slicing.

  • The sieve[0:2] = False line efficiently marks 0 and 1 as non-prime in a single operation
  • Array slicing with sieve[i*i::i] = False marks all multiples of prime numbers in one step instead of using loops
  • np.where(sieve)[0] converts the boolean mask into an array of prime numbers

This NumPy implementation runs significantly faster than pure Python approaches because it leverages optimized C-level array operations. The vectorized operations process multiple array elements simultaneously instead of one at a time.

Using prime numbers in hash_function for data distribution

Prime numbers help create efficient hash functions that distribute data evenly across storage tables by using their unique mathematical properties to minimize collisions between different input values.

def hash_function(key, table_size):
    prime = 31
    hash_value = 0
    for char in str(key):
        hash_value = (hash_value * prime + ord(char)) % table_size
    return hash_value

print(hash_function("hello", 101))
print(hash_function("world", 101))

This hash_function transforms any input key into a numerical value within a specified table size range. The function uses the prime number 31 as a multiplier to create a unique mathematical fingerprint for each input string.

  • Each character in the input gets converted to its ASCII value using ord()
  • The function accumulates these values through multiplication and addition
  • The % table_size operation ensures the final hash stays within bounds

The algorithm generates different output values for similar inputs like "hello" and "world". This distribution helps prevent value clustering when storing data in hash tables or dictionaries.

Creating RSA encryption with the encrypt_message function

The encrypt_message function demonstrates RSA encryption by using two prime numbers to create a secure public key that transforms readable text into encoded numerical values.

def encrypt_message(message, p, q):
    n = p * q
    e = 65537  # Common public exponent
    
    # Convert message to numbers and encrypt
    return [pow(ord(char), e, n) for char in message]

encrypted = encrypt_message("hi", 61, 53)
print(f"Encrypted message: {encrypted}")

The encrypt_message function implements a basic form of RSA encryption by using two prime numbers (p and q) to create a secure key. It multiplies these primes to generate n, which forms part of the public key along with the fixed exponent e = 65537.

  • Each character in the input message converts to its ASCII value using ord()
  • The function encrypts these values using modular exponentiation with pow(ord(char), e, n)
  • A list comprehension processes each character and returns the encrypted values

The example encrypts the message "hi" using the prime numbers 61 and 53. The output is a list of encrypted numerical values that can only be decrypted with the corresponding private key.

Common errors and challenges

Developers often encounter three critical challenges when implementing prime number functions in Python: handling edge cases, managing computational costs, and fixing indexing issues.

Handling negative numbers in is_prime function

Negative numbers pose a unique challenge for prime number functions. Many implementations fail to properly validate negative inputs, leading to unexpected behavior or incorrect results. The is_prime() function below demonstrates this common pitfall.

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

print(is_prime(-7))  # Will this work correctly?

The is_prime() function lacks explicit validation for negative numbers. While the n <= 1 check catches them, this approach doesn't clearly communicate to users why negative numbers can't be prime. Let's examine a more robust implementation.

def is_prime(n):
    # Prime numbers are positive integers greater than 1
    if n < 2:  # Clearer condition to handle negatives
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

print(is_prime(-7), is_prime(7))  # False True

The improved is_prime() function replaces the ambiguous n <= 1 check with a more explicit n < 2 condition. This change makes the code's intent clearer. Prime numbers must be positive integers greater than 1. The function now handles negative inputs correctly and communicates the mathematical definition more precisely.

  • Watch for this issue when validating user inputs or processing data from external sources
  • Remember that mathematical functions often need explicit boundary conditions
  • Consider adding input validation with descriptive error messages for production code

Avoiding performance traps with large prime checks

Testing large numbers for primality can create significant performance bottlenecks when using naive approaches. The is_prime() function below demonstrates a common inefficiency that occurs when checking every possible divisor up to n-1.

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, n):  # Testing all numbers up to n-1
        if n % i == 0:
            return False
    return True

# This will be extremely slow for large numbers
print(is_prime(1000003))

The is_prime() function checks every number from 2 to n-1 as potential divisors. This approach wastes computational resources by testing far more numbers than necessary. The code below demonstrates a more efficient solution.

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:  # Only check up to sqrt(n)
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

print(is_prime(1000003))  # Much faster check

The optimized is_prime() function dramatically improves performance by implementing three key optimizations. It immediately returns results for small numbers, checks divisibility by 2 and 3 upfront, and only tests potential divisors up to the square root of the input number.

  • The i * i <= n condition limits checks to the square root instead of testing all numbers
  • Incrementing by 6 with i += 6 skips many non-prime candidates
  • Early returns for small numbers and common divisors prevent unnecessary calculations

Watch for this performance trap when working with large numbers or processing many values in loops. The difference in execution time becomes significant as input sizes grow.

Fixing off-by-one errors in the sieve_of_eratosthenes function

Off-by-one errors frequently plague implementations of the Sieve of Eratosthenes algorithm. These subtle bugs occur when array sizes or loop bounds don't perfectly align with the mathematical requirements. The code below demonstrates two common indexing mistakes that lead to missing prime numbers.

def sieve_of_eratosthenes(limit):
    sieve = [True] * limit  # Array is too small
    sieve[0] = sieve[1] = False
    
    for i in range(2, int(limit**0.5)):  # Missing +1 in bound
        if sieve[i]:
            for j in range(i*i, limit, i):
                sieve[j] = False
                
    return [i for i, is_prime in enumerate(sieve) if is_prime]

print(sieve_of_eratosthenes(10))

The sieve array lacks space for the limit number itself. The square root loop bound misses the final value. These indexing issues cause the function to incorrectly identify prime numbers. The corrected implementation appears below.

def sieve_of_eratosthenes(limit):
    sieve = [True] * (limit + 1)  # Correct size
    sieve[0] = sieve[1] = False
    
    for i in range(2, int(limit**0.5) + 1):  # Correct bound
        if sieve[i]:
            for j in range(i*i, limit + 1, i):
                sieve[j] = False
                
    return [i for i, is_prime in enumerate(sieve) if is_prime]

print(sieve_of_eratosthenes(10))  # [2, 3, 5, 7]

The corrected sieve_of_eratosthenes function fixes two critical indexing issues. Creating the sieve array with limit + 1 elements ensures space for all numbers up to the limit. Adding the + 1 to the square root loop bound prevents missing the final value during prime number identification.

  • Watch for array size mismatches when implementing algorithms that need to store values up to a specific limit
  • Double-check loop bounds when working with mathematical sequences or ranges
  • Test edge cases near array boundaries to catch potential off-by-one errors early

FAQs

What is the simplest way to check if a single number is prime in Python?

The most straightforward way to check for prime numbers in Python uses trial division with a simple for loop. A number is prime when it's only divisible by 1 and itself. We can test this by checking if any smaller numbers divide evenly into it using the modulo operator %.

Here's the logic: loop through numbers from 2 to the square root of your target number. If any number divides evenly (remainder is 0), it's not prime. This approach works efficiently because any factor larger than the square root would pair with a smaller factor we've already checked.

How can I use the 'math' module to make prime checking more efficient?

The math.sqrt() function helps you check prime numbers efficiently by limiting the divisibility test range. Instead of checking all numbers up to n, you only need to check up to its square root. This works because if n has a factor larger than its square root, it must also have a corresponding factor below the square root.

  • Use math.floor() to get a clean integer cutoff point for your testing range
  • Combine with a modulo operator (%) to test divisibility
  • Start checking from 2 to catch even numbers early

What does the modulo operator do when checking for prime numbers?

The % (modulo) operator helps identify prime numbers by checking for divisibility. When dividing a number by potential factors, % returns zero if there's no remainder, indicating the number isn't prime. For example, testing if 7 is prime requires checking remainders when divided by numbers 2 through 6.

This works because prime numbers have exactly two factors: 1 and themselves. Any number that yields a remainder of 0 when used with % reveals an additional factor, disqualifying the tested number from being prime.

Why do we only need to check divisors up to the square root of a number?

When checking if a number n is divisible by another number, we only need to check up to its square root. This works because divisors come in pairs—if a divides n, there must be a corresponding b where a * b = n. One of these numbers will always be less than or equal to the square root of n.

Consider 100: its divisor pairs are 1,100 and 2,50 and 4,25 and 5,20 and 10,10. We only need to check numbers up to 10 (square root of 100) to find all divisors.

What happens when you try to check if negative numbers or zero are prime?

Prime numbers must be positive integers greater than 1. When you check if a negative number or zero is prime, most algorithms will return false immediately. This aligns with the mathematical definition: prime numbers must have exactly two distinct positive divisors—1 and themselves.

Negative numbers can't be prime because they have negative divisors. Zero isn't prime because it has infinitely many divisors. These fundamental properties shape how primality testing functions work in practice.

🏠