How to Efficiently Generate an Infinite Stream of Prime Numbers in Python?

How to implement an efficient infinite generator of prime numbers in Python?

An efficient way to generate an infinite series of prime numbers is to use the Sieve of Eratosthenes, which eliminates non-prime numbers by iteratively marking their multiples. While this method is effective, it requires a lot of memory to store the marked numbers.

erat2

Here's the erat2 function from Python's standard library's cookbook, which can be used to generate an infinite series of prime numbers:

import itertools as it
def erat2( ):
    D = {  }
    yield 2
    for q in it.islice(it.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            # old code here:
            # x = p + q
            # while x in D or not (x&1):
            #     x += p
            # changed into:
            x = q + 2*p
            while x in D:
                x += 2*p
            D[x] = p

erat2a

The erat2 function can be further optimized by avoiding unnecessary checks:

import itertools as it
def erat2a( ):
    D = {  }
    yield 2
    for q in it.islice(it.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            # old code here:
            # x = p + q
            # while x in D or not (x&1):
            #     x += p
            # changed into:
            x = q + 2*p
            while x in D:
                x += 2*p
            D[x] = p

erat3

For even faster performance, the erat3 function takes advantage of the fact that all primes (except 2, 3, and 5) modulo 30 result in only eight specific numbers. This significantly reduces the number of checks needed during the sieving process:

import itertools as it
def erat3( ):
    D = { 9: 3, 25: 5 }
    yield 2
    yield 3
    yield 5
    MASK= 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0,
    MODULOS= frozenset( (1, 7, 11, 13, 17, 19, 23, 29) )

    for q in it.compress(
            it.islice(it.count(7), 0, None, 2),
            it.cycle(MASK)):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            x = q + 2*p
            while x in D or (x%30) not in MODULOS:
                x += 2*p
            D[x] = p

These optimizations can result in significant performance improvements, especially when generating large prime numbers.

The above is the detailed content of How to Efficiently Generate an Infinite Stream of Prime Numbers in Python?. For more information, please follow other related articles on the PHP Chinese website!