Geek Answers Handbook

Python sieve algorithm optimization Eratosthenes

I am trying to realize the Sieve of Eratosthenes. The result seems correct (minus the “2” to be added), but if the input to the function is more than 100KB or so, it seems like it takes too much time. How can I optimize this feature?

def sieveErato(n):
     numberList = range(3,n,2)

     for item in range(int(math.sqrt(len(numberList)))):
            divisor = numberList[item]
            for thing in numberList:
                    if(thing % divisor == 0) and thing != divisor:
                            numberList.remove(thing)
    return numberList
+2
source share
6 answers

- . ( ) , . , , , , n:

def sieve(n):
    m = (n-1) // 2
    b = [True]*m
    i,p,ps = 0,3,[2]
    while p*p < n:
        if b[i]:
            ps.append(p)
            j = 2*i*i + 6*i + 3
            while j < m:
                b[j] = False
                j = j + 2*i + 3
        i+=1; p+=2
    while i < m:
        if b[i]:
            ps.append(p)
        i+=1; p+=2
    return ps

, n. j , 3, 5, 7, 9,... 0, 1, 2, 3,... b .

http://ideone.com/YTaMB, .

+1

, . , , 2 . . 3 . . 4 - , . n + 1, .

, . , . ( ) 2 . , .

, : http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

0

: dengerous...

    if(thing % divisor == 0) and thing != divisor:

test lighter, , , 'divisor', :

for thing in numberList_fromDivisorOn:
    if(thing % divisor == 0):
        numberList.remove(thing)
0

: - Primes Python, @MAK, , :

def primes_sieve2(limit):
    a = [True] * limit               # Initialize the primality list
    a[0] = a[1] = False
    sqrt = int(math.sqrt(limit))+1
    for i in xrange(sqrt):
        isprime = a[i]
        if isprime:
            yield i
            for n in xrange(i*i, limit, i):     # Mark factors non-prime
                a[n] = False
    for (i, isprime) in enumerate(a[sqrt:]):
        if isprime:
            yield i+sqrt
0

if unlimited memory and time are specified, the following code prints all primes. and he will do it without using a trial unit. it is based on the haskell code in the document: Genuine sieve of Eratosthenes Melissa E. O'Neill

from heapq import heappush, heappop, heapreplace
def sieve():
    w = [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]
    for p in [2,3,5,7]: print p
    n,o = 11,0
    t = []
    l = len(w)
    p = n
    heappush(t, (p*p, n,o,p))
    print p
    while True:
        n,o = n+w[o],(o+1)%l
        p = n
        if not t[0][0] <= p:
            heappush(t, (p*p, n,o,p))
            print p
            continue
        while t[0][0] <= p:
            _, b,c,d = t[0]
            b,c = b+w[c],(c+1)%l
            heapreplace(t, (b*d, b,c,d))
sieve()
0
source

This code takes 2 seconds to generate primes less than 10 M (this is not mine, I found it on Google)

def erat_sieve(bound):
    if bound < 2:
        return []
    max_ndx = (bound - 1) // 2
    sieve = [True] * (max_ndx + 1)
    #loop up to square root
    for ndx in range(int(bound ** 0.5) // 2):
        # check for prime
        if sieve[ndx]:
            # unmark all odd multiples of the prime
            num = ndx * 2 + 3
            sieve[ndx+num:max_ndx:num] = [False] * ((max_ndx-ndx-num-1)//num + 1)
    # translate into numbers
    return [2] + [ndx * 2 + 3 for ndx in range(max_ndx) if sieve[ndx]]
0
source

More articles:


All Articles