FediPrimes/sieve.py

# Sieve of Eratosthenes, in python

from numpy import array, zeros, int8
from time import process_time

def sieve(to):
    """Construct a sieve of Eratosthenes up to the value of 'to'; return all
    primes below this number.
    """
    zarr = zeros(to, int8)
    zarr[0:2] = 1
    for i in range(2, to):
        if zarr[i] == 1:
            continue
        for x in range(i, ((to - 1) // i) + 1):
            zarr[i * x] = 1
    avals = array(range(to))
    return avals[zarr[range(to)] == 0]

def sieval(to):
    """Run sieve algorithm up to 'to'; return process time, number of primes,
    and last prime calculated (in that order).

    'to' must be greater than 2.
    """
    t1 = process_time()
    sh = sieve(to)
    te = process_time() - t1
    ls = len(sh)
    return te, ls, sh[ls - 1]

def sievemsg(to):
    """Format sieval output for sieve up to 'to'

    'to' must be greater than 2.
    """
    t, n, l = sieval(to)
    rs = ("There are {1} prime numbers smaller than {3}; the largest is {2}. This "
        "calculation took {0:.2f} seconds via the sieve of "
        "Eratosthenes.".format(t, n, l, to))
    return rs