2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Note: I edited my code because I realized I had uploaded the python-2.x implementation. I have made a few adjustments to make it run under python-3.x. Thanks \$\endgroup\$ – daOnlyBG Dec 17 '19 at 7:15
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Thanks to your bitarray suggestion, my Segmented Sieve is now slower than the optimized Sieve of Eratosthenes for the big number I'm trying to calculate, lol. I'm guessing if I recoded the Segmented Sieve using bitarrays, I could (probably) optimize it further? \$\endgroup\$ – daOnlyBG Dec 17 '19 at 17:28
  • 1
    \$\begingroup\$ Whoops! Sorry about that; my bad. 8^p I didn't look too much into your Segmented Sieve implementation, but bitarray may speed that up too. You'll have to change candidates = list(range(low_val, top_val+1, 2)) from a list of numbers to a bitarray of flags, which is good because you are treating them like flags anyway with candidates[i] = False, but will need to turn them back into numbers for seed_primes += [x for x in candidates if (x and x < high)]. Something like seed_primes += [low_val + index*2 for index, flag in enumerate(candidates) if flag]. \$\endgroup\$ – AJNeufeld Dec 17 '19 at 17:40

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.