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

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

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

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

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

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

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

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

проверьте зажигалку, разделив ее на цикл, который прерывается, когда вы дойдете до индекса 'divisor', а затем тест:

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

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

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

если даны неограниченные память и время, следующий код напечатает все простые числа. И сделает это без пробного деления. он основан на коде 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()