Python 3 - удаление элементов из списка во время итерации (сито Эратосфена) - PullRequest
Новая
       11

Python 3 - удаление элементов из списка во время итерации (сито Эратосфена)

0 голосов
/ 31 августа 2018

Я строю программу для поиска всех простых чисел, меньших числа n, используя алгоритм сита Эратосфена с использованием python. Алгоритм сначала создает список чисел от 2 до n, затем выполняет итерацию по списку, удаляя первый доступный элемент и соответствующие кратные числа. Проблема в том, что я, кажется, не получаю правильный результат, поступая таким образом. Буду также признателен за любые предложения по улучшению производительности.

Это алгоритм: 

def primes(max):
    '''The sieve of Eratosthenes
    Algorithm to find all primes smaller than max'''
    init = time.clock()
    allNum = [a for a in range(2, max+1)]
    primes = []
    for n in allNum:
        # remove all multiples of prime n
        toRemove = (a for a in range(n, max+1, n) if a in allNum)
        for i in toRemove:
            print('toRemove:', i)
            allNum.remove(i)
        # add the prime to the list
        primes.append(n)

    deltaT = time.clock() - init
    print('Time taken to process:', deltaT)
    return primes

(решено) Вот как я это изменил: 

while len(allNum) != 0:
    prime = allNum[0]
    # remove all multiples of prime
    toRemove = (a for a in range(prime, max+1, prime) if a in allNum)
    for i in toRemove:
        print('toRemove:', i)
        allNum.remove(i)
    # add the prime to the list
    primes.append(prime)

Ответы [ 3 ]

0 голосов
/ 31 августа 2018

Когда вы перебираете список, вы ссылаетесь на каждое смещение, а не на каждое значение. Например, когда вы получите первый результат, если он квалифицирует и удаляет значение, все последующие значения сдвигаются вперед и ваши смещения увеличиваются. Ваше смещение теперь равно индексу 1 (база 0). Но вы только что удалили индекс 0, и все переместилось вперед Вы по сути пропустили второе число. 

0$ python3
Python 3.4.8 (default, Mar 23 2018, 10:04:27)
[GCC 4.8.5 20150623 (Red Hat 4.8.5-16)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> [a for a in range(1, 20)]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
>>> the_list = [a for a in range(1, 20)]
>>> for a in the_list:
...     the_list.remove(a)
...
>>> the_list
[2, 4, 6, 8, 10, 12, 14, 16, 18]
>>>
0 голосов
/ 31 августа 2018

Альтернативой, которая является более быстрой, является создание списка логических значений (все True) и установка их в False с использованием алгоритма. Простые числа - это все индексы в списке, которые остаются верными: 

def primes(max):
    mask = [True for i in range(0,max + 1)]
    for num in range(2,max):
        if not mask[num]:
            continue
        for multiple in range(num*2, max+1, num):
            mask[multiple] = False
    primes = [i for i,mask_value in enumerate(mask) if mask_value]
    return primes[2:]
0 голосов
/ 31 августа 2018

Я не верю, что вы можете изменить список при его итерации.

Вы можете переключиться на цикл while, который выполняется до тех пор, пока в вашем исходном списке остаются любые числа. Для каждой итерации вы удаляете хотя бы первое число: если оно является простым, вы перемещаете его в свой список простых чисел, если это не так, вы удаляете его и все его кратные.

...