How to find prime numbers in Python

Prime numbers are crucial in fields like cryptography. Python offers efficient ways to identify them. This task helps you build foundational logic and problem-solve skills for complex algorithms.

In this article, you'll explore several techniques to find prime numbers. You'll get practical tips, see real-world applications, and receive debugging advice to help you master this essential programming concept.

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(n) function implements a basic trial division algorithm. It checks for factors by iterating from 2 up to the number itself. If any number in this range divides n evenly—checked using the modulo operator %—the function immediately concludes n is not prime and returns False.

• The initial check, if n <= 1:, handles the mathematical definition that prime numbers must be greater than 1.
• The final return True is critical. It only executes if the loop finishes without finding any factors, confirming the number's primality.

Basic prime number techniques

Building on the is_prime function, you can use more efficient loops, find all primes within a certain range, and even write more concise code.

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 of is_prime is much faster because it eliminates unnecessary checks. It quickly handles small numbers and then immediately rules out any multiples of 2 or 3. The real efficiency comes from two key optimizations:

• The loop only runs as long as i * i <= n. This is because any factor larger than the square root of n would have a corresponding factor smaller than it.
• By incrementing i by 6, the loop only checks numbers of the form 6k ± 1 (like 5, 7, 11, and 13), which are the only possible prime factors left.

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(limit) function builds a list of all primes up to a specified number. It uses a nested loop to test each number for primality. The function's logic hinges on a clever use of Python's for...else syntax.

• An inner loop searches for factors. If one is found, break exits the loop immediately.
• The else clause only runs if the inner loop finishes without a break. This confirms the number has no factors other than 1 and itself, so it's appended to the primes 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 way to build lists from existing sequences. The expression [num for num in range(2, 30) if is_prime(num)] generates a list by filtering numbers from 2 to 29, keeping only those that pass the is_prime check.

• The updated is_prime function is a compact one-liner that leverages Python's built-in all() function.
• all() returns True only if every item it checks is true. Here, it confirms that n % i != 0 for every potential divisor, meaning the number is prime.

Advanced prime number algorithms

While simple trial division works, more sophisticated algorithms are essential for finding primes efficiently at a much larger scale.

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. It works by creating a boolean list—the "sieve"—and initially assuming all numbers up to a limit are prime. It then progressively eliminates composite numbers.

• The function initializes a list called sieve where every index is set to True, then correctly marks 0 and 1 as False.
• It iterates from 2 up to the square root of the limit. For each number i that's still considered prime, it marks all of its multiples as False, starting from i*i.
• Finally, a list comprehension scans the sieve and returns the indices of all remaining True values.

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]

Unlike the previous methods, the Miller-Rabin test is a probabilistic algorithm. It doesn't prove primality with absolute certainty but determines if a number is likely prime. This approach is incredibly fast and efficient, especially for very large numbers used in fields like cryptography.

• The main function, miller_rabin, repeatedly calls a helper, miller_test, for a number of rounds set by the k parameter.
• Each test uses a random number to check for mathematical properties that all primes must satisfy. If a number fails even one test, it's definitely composite. If it passes all rounds, it's considered prime with extremely high probability.

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 uses the NumPy library to run a highly optimized version of the Sieve of Eratosthenes. This approach is much faster than using standard Python lists, especially for large limits, because it takes advantage of vectorized operations.

• It creates a boolean array with np.ones(), where each index represents a number.
• The key optimization is sieve[i*i::i] = False. This uses NumPy's array slicing to mark all multiples of a prime as False in one go, avoiding a slow Python loop.
• Finally, np.where() quickly finds the indices that are still True and returns them as the final list of primes.

Move faster with Replit

Replit is an AI-powered development platform that transforms natural language into working applications. You can describe what you want to build, and Replit Agent creates it—complete with databases, APIs, and deployment.

For the prime number algorithms we've explored, Replit Agent can turn them into production-ready tools:

• Build a primality testing calculator that uses the miller_rabin test for large numbers.
• Create a prime factorization utility that breaks down any integer into its prime components.
• Deploy a simple API that generates a list of primes up to a specified limit using an optimized sieve like prime_sieve_numpy.

Describe your app idea, and Replit Agent writes the code, tests it, and fixes issues automatically, all in your browser.

Common errors and challenges

Writing prime number functions can introduce subtle bugs, but most are easy to fix once you know what to look for.

Handling negative numbers in is_prime function

A frequent oversight is forgetting that prime numbers are, by definition, natural numbers greater than 1. Your is_prime function should immediately return False for any input less than or equal to 1. An initial check like if n <= 1: handles negative numbers, zero, and one correctly, preventing unexpected behavior and logical errors.

Avoiding performance traps with large prime checks

While a simple trial division loop is intuitive, it becomes extremely slow for large numbers. A major performance trap is checking for factors all the way up to n. You can make your function dramatically faster by only checking up to the square root of n. If a number has a factor larger than its square root, it must also have a corresponding factor that is smaller, so you would have already found it.

Fixing off-by-one errors in the sieve_of_eratosthenes function

Off-by-one errors are common when implementing the sieve. To find primes up to a certain limit, your boolean list must be of size limit + 1 to include an index for the limit itself. Forgetting this can cause IndexError exceptions or incorrect results. Similarly, ensure your loops cover the correct ranges—for example, using range(i*i, limit + 1, i) correctly marks multiples without going out of bounds.

Handling negative numbers in is_prime function

Prime numbers are strictly positive integers greater than one. But what happens if your is_prime function receives a negative number? Without a specific check, the logic can produce unexpected or incorrect results. The code below demonstrates this potential 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 expression int(n**0.5) creates a pitfall. For a negative n, this calculation is invalid and would cause an error, preventing the loop from running. The following code demonstrates how to properly structure the function to avoid this.

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 is_prime function uses the condition if n < 2: to immediately filter out negative numbers, zero, and one. This check is crucial because it prevents the int(n**0.5) calculation from failing on a negative input, which would cause an error. By validating inputs at the start, you make your function more robust. It’s a good practice to apply this logic whenever a mathematical operation has a limited domain, like square roots.

Avoiding performance traps with large prime checks

Your program can slow to a crawl when testing very large numbers for primality if you're not careful. The most common performance trap is using a simple loop that checks every single number up to your target, which is computationally expensive and unnecessary.

The following is_prime function illustrates this issue perfectly. Notice how its loop runs all the way to n, causing a significant delay when given a large input.

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 loop for i in range(2, n): creates a bottleneck, forcing millions of redundant checks for a large number like 1,000,003. This brute-force method is highly inefficient. The corrected code below offers a much smarter approach.

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

This corrected function boosts performance by drastically cutting down on checks. It's a smart solution for large numbers where a simple loop would be too slow.

• It quickly eliminates multiples of 2 and 3.
• The loop only runs while i * i <= n, which is far more efficient than checking up to n.
• Incrementing with i += 6 lets you skip over many non-prime numbers in each step.

Fixing off-by-one errors in the sieve_of_eratosthenes function

The sieve_of_eratosthenes function is powerful, but it's also prone to off-by-one errors. These subtle mistakes in array sizing or loop ranges can cause your function to miss primes, include non-primes, or even crash with an IndexError.

The code below contains a few of these classic mistakes. See if you can spot where the logic goes wrong.

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 is one element too short, so it can't check the limit number. The loops also end early, failing to mark all necessary multiples and producing an incomplete list of primes. The following implementation shows how to resolve these subtle but critical errors.

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 critical off-by-one errors. It’s a reminder to be precise with ranges in array-based algorithms, especially when mapping numbers to indices.

• The sieve list is sized to limit + 1 to correctly include the limit value, preventing an IndexError.
• Loop boundaries are also extended to limit + 1, ensuring all multiples are marked and no primes are missed within the range.

Real-world applications

With a solid grasp of these algorithms, you can see how prime numbers power everything from data distribution to secure encryption.

Using prime numbers in hash_function for data distribution

In a hash_function, a prime number acts as a special multiplier that helps scatter data evenly across a storage structure, which is crucial for preventing different items from piling up in the same spot.

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))

The hash_function turns a string key into a numerical index that fits within a given table_size. It’s a common way to map data to a specific location, like an array index, by processing the key one character at a time.

• The function iterates through each character, converting it to an integer with ord().
• It updates the hash_value by multiplying the current value by a prime and adding the new character's integer value.
• Finally, the modulo operator (% table_size) scales the result to fit within the table's bounds.

Creating RSA encryption with the encrypt_message function

The encrypt_message function shows how RSA encryption uses two prime numbers to create a public key, turning your message into a secure sequence of encrypted numbers.

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 transforms a string into a list of numbers through a mathematical process. It's built on two prime numbers, p and q, which are multiplied to create a modulus n. This value n sets the numerical boundary for the entire operation.

• A list comprehension processes your message, converting each character into its integer value with ord().
• The built-in pow() function then takes this number, raises it to the power of a fixed exponent e, and applies the modulus n—the core of the transformation.

Get started with Replit

Turn what you've learned into a real tool. Tell Replit Agent: "Build a tool that visualizes the Sieve of Eratosthenes" or "Create a web app to test large primes with Miller-Rabin."

The agent writes the code, tests for errors, and deploys your app. Start building with Replit and watch your idea become a reality.