6
\$\begingroup\$

I've implemented two prime sieves in python 3 to find all prime numbers up to an upper limit n - n exlusive. The first one is rather naive, while the second one only considers odd numbers to begin with (some clever index-arithmetic is necessary).

Naive implementation:

def naive_sieve(n):
    if n < 3:
        return []

    sieve = [False, False, True] + [True, False] * (n // 2 - 1)

    for prime in range(3, int(n**0.5) + 1, 2):
        if sieve[prime]:
            for multiple in range(prime*prime, len(sieve), 2*prime):
                sieve[multiple] = False

    return [number for number, is_prime in enumerate(sieve) if is_prime]

I actually implemented the more advanced sieve twice. One time giving every little step a sub-function with name (to get the understanding right) and the second time without all these definitions (to minimize the number of function calls).

More readable implementation

def easy_odd_sieve(n):
    if n < 3:
        return []

    def number_of_odd_nums_below(n):
        return n // 2

    def greatest_odd_number_below(n):
       return ceil(n) // 2 * 2 - 1

    def index_of_odd_number(n):
        return (n - 1) // 2

    def odd_number_from_index(i):
        return (2*i + 1)

    sieve = [0] + [1] * (number_of_odd_nums_below(n) - 1)

    for j in range(1, index_of_odd_number(greatest_odd_number_below(n ** 0.5)) + 1):
        if sieve[j]:
            for i in range(index_of_odd_number(odd_number_from_index(j) ** 2), len(sieve), odd_number_from_index(j)):
                sieve[i] = False

    return [2] + [odd_number_from_index(index) for index, is_prime in enumerate(sieve) if is_prime]

Final implementation:

def odd_sieve(n):
    if n < 3:
        return []

    sieve = [0] + [1] * (n //2 - 1)

    for j in range(1, ceil(n ** 0.5) // 2):
        if sieve[j]:
            for i in range((2*j)*(j + 1), len(sieve), 2*j + 1):
                sieve[i] = False

    return [2] + [2*index + 1 for index, is_prime in enumerate(sieve) if is_prime]

My questions regarding this code are:

  • How does my general python programming style look like?
  • Correctness. Is the code correct or did I overlook something? (I've checked that all sieves return the same list for n in range(1, 1000))
  • Naming. Are the variable names clear to the reader? What would you change?
\$\endgroup\$
1
\$\begingroup\$

Your style generally looks fine. Do run flake8 and make the edits suggested, mostly adjusting whitespace. Starting out with zero and one, then switching to False, is a bit odd.

In e.g. last line of odd_sieve(), consider turning that into a three-line list comprehension.

    sieve = [False, False, True] + [True, False] * (n // 2 - 1)

That seems to allocate lots more than sqrt(N) entries.

The function name of number_of_odd_nums_below() appears to be off-by-one, as it's missing a comment explaining one may only pass in odd numbers. With such a restriction it seems that greatest_odd_number_below() would simply become n - 2.

My personal preference is for the naive code. The fancier version feels like it's cheating. If we get to use long division, why stop at 2? Why not 3, 5, 7, 11? When (before sqrt(N)) is the right place to stop, and transition to sieving? The advantage of the sieve is that, once having constructed a bounded list of primes, it can rapidly answer lots of prime queries. It would be interesting to see a particular problem domain involving many repeated queries where a natural tradeoff really does emerge.

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.