4
\$\begingroup\$

For a project I am working on, I need to use a lot of primes, frequently. To do this, I added a cache to Will Ness's prime sieve, that stores already generated primes so getting them is quick. How can I improve this code?

def prime_sieve(): # postponed sieve, by Will Ness
    for c in (2,3,5,7):                     # original code David Eppstein,
        yield c
    sieve = {}                              # Alex Martelli, ActiveState Recipe 2002
    ps = prime_sieve()                      # a separate base Primes Supply:
    p = next(ps) and next(ps)               # (3) a Prime to add to dict
    q = p*p                                 # (9) its sQuare
    for c in count(9,2):                    # the Candidate
        if c in sieve:                      # c’s a multiple of some base prime
            s = sieve.pop(c)                # i.e. a composite ; or
        elif c < q:
            yield c                     # a prime
            continue
        else:   # (c==q):            # or the next base prime’s square:
            s=count(q+2*p,2*p)       #    (9+6, by 6 : 15,21,27,33,...)
            p=next(ps)               #    (5)
            q=p*p                    #    (25)
        for m in s:                  # the next multiple
            if m not in sieve:       # no duplicates
                break
        sieve[m] = s                 # original test entry: ideone.com/WFv4f

class cached_primes:
    def __init__(self):
        self.prime_gen = prime_sieve()
        self.vals = [2]
        next(self.prime_gen)

    def get(self, start=2, end=float('inf')):
        vals = self.vals

        lo = self.get_ind(start)
        if vals[-1] >= end:
            hi = self.get_ind(end)
            yield from islice(vals, lo, hi)
            return
        else:
            while vals[-1] < end:
                if len(vals) > lo:
                    bound = len(vals)
                    yield from takewhile(lambda p: p <=end, islice(vals, lo, bound))
                    lo = bound
                vals.append(next(self.prime_gen))
        hi = self.get_ind(end)
        yield from islice(vals, lo, hi)

    def get_ind(self, x):
        if x <= 2:
            return 0
        vals = self.vals
        B = x/log(x)
        if x < 17:
            return bisect(vals, x, 0, min(len(vals), int(B)))
        return bisect(vals, x, int(B), min(len(vals), int(1.25506*B)))
\$\endgroup\$
  • 2
    \$\begingroup\$ Can you add a link to the prime sieve solution on which your code is based? \$\endgroup\$ – Martin R Jan 5 '18 at 6:23
  • \$\begingroup\$ ideone.com/WFv4f \$\endgroup\$ – Oscar Smith Jan 5 '18 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.