Attachment 10220 Details for Bug 22983 – Eratosthenes Sieve for prime numbers

Eratosthenes Sieve for prime numbers

sieve.py (text/x-python), 985 bytes, created by Len Lawrence on 2018-06-03 12:40:43 CEST

(hide)

Description:

Filename:

MIME Type:

Creator: Len Lawrence

Created: 2018-06-03 12:40:43 CEST

Size: 985 bytes

patch

obsolete

>#!/bin/env python3
>
>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( 300 )
>exit( )

#!/bin/env python3

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( 300 )
exit( )

Actions: View

Attachments on bug 22983: 10219 | 10220 | 10222