Оптимизация алгоритма сита Эратосфена Python

Question

Я пытаюсь внедрить Сито Эратосфена.Выходные данные кажутся правильными (минус «2», который необходимо добавить), но если входные данные для функции больше, чем 100 КБ или около того, кажется, что это занимает слишком много времени.Как можно оптимизировать эту функцию?

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

Answer 1

Ваш алгоритм - это не сито Эратосфена. Вы выполняете пробное деление (оператор модуля) вместо вычеркивания кратных, как это делал Эратосфен более двух тысяч лет назад. Здесь - это объяснение истинного алгоритма просеивания, а ниже показана моя простая, прямая реализация, которая возвращает список простых чисел, не превышающих 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,, где она вычисляет простые числа до миллиона менее чем за секунду.

Answer 2

Этот код занимает 2 секунды для генерации простых чисел менее 10М (это не мое, я нашел это где-то в 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]]

Answer 3

если дано неограниченное количество памяти и времени, следующий код напечатает все простые числа.и он сделает это без использования пробного разделения.оно основано на коде haskell в статье: Подлинное сито эратосфена Мелиссы Э. О'Нил

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()

Answer 4

Я перешел по этой ссылке: Сито Эратосфена - Поиск простых чисел 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

Answer 5

Предупреждение: удаление элементов из итератора во время итерации может быть очень сложным ...

Вы могли бы сделать

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

проверить светлее, разбив его на петлю, которая прерывается, когда вы достигаете индекса делителя, а затем проверяет:

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

Answer 6

Вы можете попробовать так же, как Эратосфен.Возьмите массив со всеми числами, которые вам нужны, чтобы проверить порядок возрастания, перейдите к номеру 2 и отметьте его.Теперь вычеркните каждое второе число до конца массива.Затем перейдите к 3 и отметьте его.После этого поцарапайте каждый третий номер.Затем перейдите к 4 - он уже поцарапан, так что пропустите его.Повторите это для каждого n + 1, который еще не поцарапан.

В конце отмеченные числа являются главными.Этот алгоритм работает быстрее, но иногда требуется много памяти.Вы можете немного оптимизировать его, отбросив все четные числа (потому что они не простые) и добавив 2 в список вручную.Это немного исказит логику, но займет половину памяти.

Вот иллюстрация того, о чем я говорю: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes