How Can I Optimize a Simple Prime Number Generator in Python?

Optimizing a Simple Prime Number Generator in Python

The provided Python code aims to generate prime numbers but needs improvements for efficiency.

Issues with the Original Code:

1. The loop checks for divisibility but incorrectly prints the count even if it finds a divisor.
2. The continue statement terminates the current iteration but should be replaced with break to stop searching altogether when a divisor is found.

Improved Code:

import math

def main():
    count = 3
    while True:
        isprime = True
        for x in range(2, math.ceil(math.sqrt(count)) + 1):
            if count % x == 0: 
                isprime = False
                break
        if isprime:
            print(count)
        count += 1

Explanation:

• The outer loop increments the count to test for the next possible prime.
• The inner loop now runs up to the square root of the count, as any divisor greater than the square root will have a corresponding divisor below the square root.
• If the count is divisible by any x, the isprime flag is set to False and the inner loop breaks.
• If no divisors are found, the count is a prime and is printed.

Advanced Prime Generation:

For more efficient prime generation, the Sieve of Eratosthenes is recommended. Here's an optimized Python implementation with comments:

def gen_primes():
    D = {}
    q = 2
    while True:
        if q not in D:
            yield q
            for later in range(q * q, 1000000, q):
                D[later] = [q]
        else:
            for later in range(q + D[q][0], 1000000, q):
                D.setdefault(later, []).append(q)
            del D[q]
        q += 1

The above is the detailed content of How Can I Optimize a Simple Prime Number Generator in Python?. For more information, please follow other related articles on the PHP Chinese website!