Attachment 13417 Details for Bug 30572 – Eratosthenes Sieve for python2

Eratosthenes Sieve for python2

sieve2.py (text/plain), 961 bytes, created by Len Lawrence on 2022-10-10 01:04:55 CEST

(hide)

Description:

Filename:

MIME Type:

Creator: Len Lawrence

Created: 2022-10-10 01:04:55 CEST

Size: 961 bytes

patch

obsolete

#!/bin/python2
import itertools

def eratosthenes(max):
    '''Yields the sequence of prime numbers via the Sieve of Eratosthenes.'''
    D = { } # map each composite integer to its first-found prime factor
    for q in itertools.count(): # q gets 2, 3, 4, 5, ... ad infinitum
         p = D.pop(q, None)
         if p is None:
             # q not a key in D, so q is prime
             # mark q squared as not-prime (with q as first-found prime factor)
             if q > 1:
                 print("q = %d" % q)
             D[q*q] = q
         else:
             # let x <- smallest (N*p)+q which wasn't yet known to be composite
             # we just learned x is composite, with p first-found prime factor,
             # since p is the first-found prime factor of q -- find and mark it
             x = p + q
             while x in D:
                 x += p
             if q > max:
                 return(0)
             D[x] = p
 
eratosthenes(70)

Actions: View

Attachments on bug 30572: 13417