How to find prime numbers in Python

Prime numbers are fundamental in computer science, with uses in cryptography and algorithm design. Python offers several efficient methods to identify them, a key skill for any developer to master.

You'll learn several techniques to identify primes, from simple loops to optimized algorithms. We'll cover practical tips, real-world applications, and debugging advice to help you write efficient and correct code.

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))--OUTPUT--True False

The is_prime function implements the fundamental definition of a prime number. It systematically checks for any factors between 2 and the input number, n, to determine if it's divisible by anything other than 1 and itself. This process is similar to finding factors of a number.

• The function first handles the edge case by immediately returning False for any number less than or equal to 1.
• It then uses a loop and the modulo operator (%) to test for divisibility. If n % i ever equals zero, a factor has been found, and the number isn't prime. Understanding using the modulo operator is crucial for this technique.
• If the loop completes without finding any factors, the number is confirmed to be prime.

Basic prime number techniques

That initial function is a great start, but you can build on it with more efficient loops and cleaner syntax to find multiple primes at once.

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))--OUTPUT--True False

This version significantly speeds up prime checking with a few clever tricks. It quickly handles small numbers and immediately rules out any multiples of 2 or 3, which are common non-primes.

• The loop only runs while i * i <= n. This is a key optimization because you only need to check for factors up to the square root of a number to determine if it's prime.
• By starting at 5 and incrementing by 6, the loop efficiently checks potential factors, skipping all multiples of 2 and 3. This technique demonstrates advanced using while loops for optimization.

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))--OUTPUT--[2, 3, 5, 7, 11, 13, 17, 19]

The get_primes function builds a list of all prime numbers up to a specified limit. It works by iterating through each number and attempting to find a factor using a nested loop.

• The function’s logic hinges on a clever Python feature—the for...else loop.
• If the inner loop finds a factor and executes a break, the else block is skipped.
• If the loop completes without a break, it means no factors were found. The else block then runs, appending the prime number to the list.

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)--OUTPUT--[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

List comprehensions offer a more concise and "Pythonic" way to create lists. This example refactors the prime-finding logic into a compact, single line of code by filtering a range of numbers.

• The is_prime function is now a one-liner using the all() function. It returns True only if n % i != 0 for all potential factors, elegantly confirming the number is prime.
• The list comprehension itself, [num for num in ... if is_prime(num)], iterates through a range and applies the is_prime function as a filter. Only numbers that return True are added to the final list.

Advanced prime number algorithms

For serious performance gains, you can graduate from basic loops to powerful algorithms like the Sieve of Eratosthenes, the Miller-Rabin test, and vectorized NumPy approaches.

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))--OUTPUT--[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

The sieve_of_eratosthenes function is a classic, highly efficient algorithm for finding all prime numbers up to a specified limit. It works by creating a boolean list, or sieve, that initially assumes every number is prime by marking it as True.

• The algorithm iterates from 2 up to the square root of the limit. For each number i that is still considered prime, it marks all of its multiples as False.
• The inner loop starts marking multiples from i*i, a key optimization that avoids redundant work.
• Finally, a list comprehension filters the sieve, collecting the indices of all values that remain True.

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)])--OUTPUT--[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

The miller_rabin function is a probabilistic test, meaning it doesn't guarantee a number is prime but confirms it with a very high probability. This trade-off makes it incredibly fast for checking large numbers where deterministic methods are too slow. The algorithm relies on generating random numbers for its probabilistic approach.

• The logic is split into a helper, miller_test, which performs a single check using a random base number.
• The main miller_rabin function runs this test k times. More rounds increase the certainty of the result.
• If the function returns False, the number is definitely composite. If it returns True, it's almost certainly prime.

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))--OUTPUT--[ 2 3 5 7 11 13 17 19 23 29]

The prime_sieve_numpy function leverages the NumPy library to perform a highly optimized Sieve of Eratosthenes. Instead of using standard Python loops, it relies on vectorized operations, which process entire arrays at once for a significant speed boost. It's a powerful demonstration of how numerical libraries can accelerate common algorithms, perfect for vibe coding.

• The core of the optimization is sieve[i*i::i] = False. This single line uses NumPy's advanced slicing to mark all multiples of i as non-prime simultaneously.
• Finally, np.where(sieve)[0] efficiently collects the indices of all remaining True values, giving you the final list of primes.

Move faster with Replit

Replit is an AI-powered development platform that comes with all dependencies pre-installed, so you can skip setup and start coding instantly. Instead of just piecing together techniques like the prime-finding functions we've covered, you can use Agent 4 to build complete applications directly from a description.

• A primality testing utility that uses the miller_rabin test to quickly verify large numbers for cryptographic applications.
• A prime number generator that uses the sieve_of_eratosthenes to create lists of primes for mathematical modeling or educational tools.
• A factorizer tool that breaks down any given number into its prime factors, a common feature in number theory calculators.

Simply describe your app, and Replit will write the code, test it, and fix issues automatically, all within your browser.

Common errors and challenges

Even with the right algorithms, you can run into subtle bugs and performance issues when checking for prime numbers in Python.

• Handling negative numbers in an is_prime function. By definition, prime numbers are positive integers greater than 1. Your function must account for this, as inputs like 0, 1, or any negative number are not prime. Failing to add a check like if n <= 1: return False can lead to incorrect results, since loops starting from 2 won't even run for these values.
• Avoiding performance traps with large prime checks. A simple loop that checks for factors all the way up to n is a classic performance trap. While it works for small numbers, it becomes painfully slow for large inputs. The key optimization is to only check for factors up to the square root of n, since any factor larger than that would have a corresponding smaller factor you would have already found.
• Fixing off-by-one errors in the sieve_of_eratosthenes function. Off-by-one errors are a common pitfall in array-based algorithms. For example, creating the boolean list as [True] * limit instead of [True] * (limit + 1) will cause an IndexError because the list index won't match the number you're checking. Ensuring your list size and loop ranges are correct is critical for the Sieve to work as intended.

Handling negative numbers in is_prime function

Prime numbers are defined as positive integers greater than 1, a rule that's easy to overlook when coding. Your is_prime function must explicitly reject negative numbers, 0, and 1 to prevent incorrect outputs. See how the following code handles a negative input.

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 code handles the negative input correctly. The if n <= 1: condition catches -7 and returns False immediately, preventing the loop from running and causing unexpected behavior. Check the output to see the result.

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 corrected code refines the initial check to n < 2, a clearer way to enforce the rule that primes must be positive integers greater than 1. This single condition correctly handles negative numbers, 0, and 1. It's a crucial first step in any primality function, as it prevents the main loop from running with invalid inputs and producing incorrect results. Always validate your inputs first to avoid subtle bugs down the line.

Avoiding performance traps with large prime checks

While a basic loop works for small numbers, it hits a wall with large inputs. Checking for factors all the way up to n is a classic performance trap that makes your code incredibly slow. The following example demonstrates this exact problem.

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 for i in range(2, n): loop is the bottleneck. For a number like 1000003, it performs almost a million checks, making the function unacceptably slow. See how a simple optimization fixes this.

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 function is dramatically faster because it only checks for factors up to the square root of n, using the condition while i * i <= n:. It also immediately rules out multiples of 2 and 3. The loop then efficiently steps through remaining candidates by increments of 6. This approach is crucial whenever your code needs to verify large numbers without getting bogged down in millions of unnecessary checks.

Fixing off-by-one errors in the sieve_of_eratosthenes function

Off-by-one errors are a classic stumbling block in array-based algorithms like the sieve_of_eratosthenes. A mistake in list size or loop range can cause an IndexError or produce incorrect results. The following code contains two subtle bugs. See if you can spot them.

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 list is one element too short, causing index errors. The main loop also stops just before the square root, failing to mark all non-primes. Check the corrected code below to see how these subtle but critical mistakes are resolved.

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 resolves two common off-by-one errors that can break the algorithm. These bugs often appear in array-based logic where list indices must align perfectly with the numbers they represent.

• The sieve list is now created with [True] * (limit + 1) so its indices go up to the limit, preventing an IndexError.
• The loop range is corrected to int(limit**0.5) + 1 because range excludes the upper bound, ensuring the check includes the square root.

Real-world applications

Beyond the algorithms and bug fixes, prime numbers are crucial for real-world tasks like secure encryption and efficient data distribution.

Using prime numbers in hash_function for data distribution

In a hash_function, a prime number is often used as a multiplier to help distribute keys more uniformly, which minimizes the chances of collisions in a hash table.

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 turns any given key into a consistent numerical index, designed to fit within a hash table of a specific table_size. It processes the key one character at a time to generate a value that's sensitive to the order of the characters.

• The function loops through each character, converting it to its numerical representation using ord().
• Each character's value is mixed into the running hash_value using multiplication with a prime number, 31.
• Finally, the modulo operator (%) constrains the result to fit within the specified table_size.

Creating RSA encryption with the encrypt_message function

The encrypt_message function demonstrates a core principle of RSA encryption: using two prime numbers to create a public key that securely transforms a message into an unreadable format.

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 shows a simplified RSA encryption process. It multiplies two prime numbers, p and q, to create the public key modulus n. A list comprehension then iterates through the message, converting each character into a number with ord() before encrypting it - a perfect example of how AI coding can help implement complex cryptographic functions.

• The pow() function efficiently calculates (character_value ** e) % n for each character, where e is a fixed public exponent.
• This process transforms the original message into a list of encrypted numbers, making it unreadable without the corresponding private key. These principles extend to more advanced file encryption techniques.

Get started with Replit

Now, turn these algorithms into a real tool. Describe what you want to Replit Agent, like "build a prime factorization calculator" or "create a primality testing web app using the Miller-Rabin test."

The Agent writes the code, tests for errors, and deploys your app directly from your browser. Start building with Replit.