Fastest method to list all Prime Numbers in Python

Understanding the Problem: Prime Number Generation

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Generating prime numbers is a classic computer science problem. When a user inputs a limit (e.g., 100,000), our script needs to find and list all prime numbers from 2 up to that limit.

The naive way to approach this is to check every single number to see if it is divisible by any smaller number. While this logic is simple to implement, it is computationally expensive. Let's look at the standard iterative approach first.

Method 1: The Iterative Approach (Trial Division)

This first method is the most common approach taught to beginners. It involves iterating through every number up to the user input and checking if it has any divisors. To optimize slightly, we only check divisors up to the square root of the number (int(i**0.5) + 1), because a larger factor of the number would necessarily be a multiple of a smaller factor that has already been checked.

usr_input = int(input("Enter a number: "))
prime_numbers = []

for i in range(2, usr_input+1):
  for j in range(2, int(i**0.5)+1):
    if i % j == 0:
      break
  else:
    prime_numbers.append(i)

print(prime_numbers)

How this method works:

• We initialize an empty list prime_numbers to store our results.
• We use a for loop to iterate through every number i from 2 up to the user's limit.
• For each number, a nested for loop checks if i is divisible by any number j up to its square root.
• If a divisor is found (i % j == 0), we break out of the inner loop because the number is not prime.
• The else block attached to the for loop appends the number to our list only if the loop completes without hitting the break statement.

Time Complexity: O(N √N). While acceptable for small limits (like 1,000), this method becomes noticeably slow when dealing with larger limits like 1,000,000 or beyond due to the heavy modulo division operations occurring in the nested loops.

Method 2: Sieve of Eratosthenes (The Optimized Approach)

To drastically speed up prime number generation, we can use an ancient mathematical algorithm known as the Sieve of Eratosthenes. Instead of using division to check if a number is prime, this algorithm iteratively marks the multiples of each prime number as composite (not prime), starting from 2.

This method avoids division entirely and relies on memory allocation (using a boolean array) and addition, making it blisteringly fast.

upto = int(input("Enter the limit: "))
prime_no = []

# Initialize a boolean array with 'True' for all numbers
is_prime = [True] * (upto+1)
is_prime[0] = is_prime[1] = False

# Optimization: manually mark multiples of 2 as False
for i in range(4, upto+1, 2):
  is_prime[i] = False

# Mark multiples of odd numbers starting from 3
for i in range(3, int(upto**0.5)+1, 2):
  if is_prime[i]:
    # Start marking from i squared, incrementing by 2*i to skip even numbers
    for j in range(i*i, upto+1, i*2):
      is_prime[j] = False

# Assign the remaining 'True' numbers to the 'prime_no' list
for i in range(2, upto+1):
  if is_prime[i]:
    prime_no.append(i)

print(f"Prime numbers up to {upto} are: {prime_no}")

Why this method is vastly superior:

• Boolean Arrays: We create a list of boolean True values representing our numbers. Accessing and updating boolean values in Python arrays by index is incredibly fast.
• No Division: Notice that there is no modulo (%) operator in the inner loops. The algorithm simply jumps to multiples (addition) and flips their state to False.
• Skipping Even Numbers: We handle multiples of 2 immediately, allowing the main loop to step by 2 (range(3, ..., 2)), effectively cutting the workload in half.
• Starting at the Square: When marking multiples of a prime i, we start at i*i because all smaller multiples have already been marked by smaller prime factors.

Time Complexity: O(N log log N). This is nearly linear time. For an input of 1,000,000, this method executes in a fraction of a second, whereas Method 1 will leave you staring at a hanging terminal.

Performance Comparison and Benchmarks

If you were to use Python's built-in time module to benchmark both methods for a limit of 1,000,000, the differences are staggering:

• Method 1 (Trial Division): Takes approximately 3 to 5 seconds depending on the CPU.
• Method 2 (Sieve of Eratosthenes): Completes in roughly 0.05 seconds.

That is a massive performance increase of over 100x. The second method involves more code, but the underlying algorithm relies on boolean state-toggling rather than expensive arithmetic operations. When developing backend systems or APIs, choosing the right algorithm dictates your server load and response times.

Frequently Asked Questions (FAQ)

Conclusion

While the first iterative method is easy to write and understand, it is fundamentally unsuited for large-scale operations. The Sieve of Eratosthenes is the definitive answer when you need to list all prime numbers up to a specific limit in Python. It perfectly illustrates why understanding algorithmic complexity is just as important as knowing the syntax of the programming language.

Next time you are faced with a choice between writing fewer lines of code and using a better algorithm, prioritize the efficiency of your code. Your servers (and your users) will thank you.