Further Optimizing a Segmented Sieve of Eratosthenes

Question

I've implemented a Segmented Sieve of Eratosthenes that assumes each segment is about length \$ \sqrt{N}\$ for some upper limit \$N\$.

I further optimized the function by skipping all the evens when sieving.

I'd like to know if anyone has any views or advice on further optimizing my implementation.

Note that there are three functions: the first, "SieveEratList" is a standard Sieve of Eratosthenes (to calculate primes in range \$ [1, \sqrt{N}] \$); the second, "find_first_multiple_odds", checks to find the initial index value in an interval of odd numbers (since we're skipping evens); and the third, "OptiSegment," is the optimized Segmented Sieve that calls the previous two when needed.

I'm open to any suggestions, whether it's space optimization or runtime optimization.

def SieveEratList(n):
    numbers = [False]*2+[True]*(n-2)
    result = []
    for index, prime_candidate in enumerate(numbers):
        if prime_candidate:
            result.append(index)
            for x in range(index*index, n, index):
                numbers[x] = False
    return result

def find_first_multiple_odds(p, low): 
    # O(1) 
    x = p*((low/p)+(low%p != 0))
    x += p*(x%2 == 0)
    return ((x-low)/2) 

def OptiSegment(high):
    delta = int(high**0.5)+1*(int(high**0.5)%2)

    seed_primes = SieveEratList(delta+1)
    #boolean operator checks see if "high" is square
    segment_count = int(high/delta) - 1*((high**0.5)-int(high**0.5) == 0.0) 


    for seg in range(1, segment_count+1):
        low_val = seg*delta+1
        top_val = delta*(seg+1)-1

        candidates = list(range(low_val, top_val+1, 2))
        prime_limit = top_val**0.5+1

        Q = iter(seed_primes)
        p = next(Q)
        p = next(Q)

        while p < prime_limit:
            q = find_first_multiple_odds(p, low_val)

            for i in range(q, delta/2, p):
                candidates[i] = False
            p = next(Q)

        seed_primes += [x for x in candidates if (x and x < high)]

    return seed_primes

Answer 1

Python 3.8 adds math.isqrt(). Using this, you can make a much less cryptic perfect square check:

high == math.isqrt(high) ** 2

---

Memory Optimization (speed too!)

Using a list of Boolean flags:

numbers = [False]*2 + [True]*(n-2)

is very space inefficient. You are using 28 bytes per flag! By packing 8 flags into one byte, you’d achieve a 99.5% memory usage reduction. Doing this packing yourself would be slow and awkward. Fortunately, there is a package that does this for you: bitarray.

numbers = bitarray.bitarray(n)
numbers.setall(True)
numbers[0:2] = False

Notice that slice assignment from a scalar Boolean? It gets better when you use it to cross off the multiples of a prime candidate:

if prime_candidate:
    result.append(index)
    numbers[index*index::index] = False

and done!

---

Integer division

You should really use integer division // in find_first_multiple_odds():

x = p * ((low // p) + (low % p != 0))
...
return (x - low) // 2

---

PEP-8

• use snake_case function names. UpperCase is for class names
• use a space around binary operators