Попытка решить Project Euler # 10, но код занимает * много * времени для вывода вывода

Правильная структура данных для простого сита представляет собой битовый набор, индексированный по целочисленному значению. Python не имеет одного из встроенных модулей, но поскольку ваш лимит невелик (всего 2 миллиона), регулярный список целых чисел должен соответствовать памяти, хотя его расточительность в 30 или более раз (потребуется около 9 MB, где эквивалентный битсет в C будет 250 КБ).

Важная вещь для скорости – никогда не обращаться к массиву, кроме как путем непосредственной прямой индексации (так что не удалять / удалять). Кроме того, ограничьте внешний цикл сита до sqrt (limit) и переместите цикл в следующее простое, а не следующее значение.

Так что что-то вроде этого должно быть довольно быстрым (это занимает около 2 секунд на моей старой машине в vanilla Python 2.7).

 import math, sys def prime_sieve(limit): # Mark everything prime to start primes = [1 for x in xrange(limit)] primes[0] = 0 primes[1] = 0 # Only need to sieve up to sqrt(limit) imax = int(math.sqrt(limit) + 1) i = 2 while (i < imax): j = i + i while j < limit: primes[j] = 0 j += i # Move i to next prime while True: i += 1 if primes[i] == 1: break return primes s = prime_sieve(2000000) print(sum(i for i in xrange(len(s)) if s[i] == 1)) 

Проблема заключается в следующем:

 primes.remove(i*j) 

.remove() очень неэффективен, когда вызывается в больших списках, потому что сначала он должен итерации по всему списку, чтобы определить, где, если таковые имеются, значение присутствует, а затем он должен снова перебирать часть списка для переключения все элементы после удаляемого элемента опускаются на одно место.

Существуют и другие способы использования структур данных (как для других способов использования списков, так и для других структур данных), которые будут более эффективными.

Наконец: ваш код изменяет primes одновременно с тем, как вы итерации по нему (что и делается for i in primes ). Это, как правило, считается плохой, поскольку изменение чего-то, так как оно повторяется, является потенциально неопределенным поведением.

Более эффективная идея выглядит следующим образом:

Вы начинаете со списка:

 [0,1,2,3,4,5,6,7,8,9,10] 

Вы хотите установить каждый элемент, который не является простым с 0, и сохранить простые числа.

Установите 0 и 1 на ноль, потому что они не простые. С этого момента вам нужно выполнить следующие два действия:

1) Найдите наименьшее число, которое вы еще не рассмотрели, назовем его n

2) Установите каждый n-й элемент равным 0 (но не n), так как они кратно n

Например: после того, как вы установили 0 и 1 в 0s:

 [0,0,2,3,4,5,6,7,8,9,10] 

Наименьшее значение, которое вы не учитывали, равно 2, поэтому вы устанавливаете каждый второй элемент равным нулю (но не 2):

 [0,0,2,3,0,5,0,7,0,9,0] 

Наименьшее простое число, которое вы не учитывали, равно 3, поэтому вы устанавливаете каждый третий элемент на ноль (но не на 3) и так далее …:

 [0,0,2,3,0,5,0,7,0,0,0] 

Также обратите внимание, что вам не нужно делать это для каждого простого числа, как только простые числа достигнут sqrt (limit), вы можете остановиться, потому что знаете, что все не простые числа были установлены в нули.

Например, квадратный корень из 10 (предел в этом случае) равен 3.162, это означает, что нам не нужно ничего делать, когда мы добираемся до 5, и мы делаем это в этой точке. Но почему? Мы используем каждое простое число, чтобы установить его кратность в нули, потому что эти кратность не являются штрихами; однако, поскольку 5 больше квадратного корня из 10, любое кратное 5 должно быть кратно числу, меньшему 5, и, следовательно, уже было установлено на 0.

Предположим, что наш начальный диапазон был от 20 до 20. Квадратный корень из 20 меньше 5, поэтому нам не нужно проверять 5, потому что все кратные 5: 5 * 2 = 10, 5 * 3 = 15, 5 * 2 * 2 = 20 кратны меньшим простым числам, и мы уже установили их в 0.

Вот простая версия Сита Эратосфена, приспособленная для вычисления суммы вместо формирования списка простых чисел, меньших n :

 def sumPrimes(n): sum, sieve = 0, [True] * n for p in range(2, n): if sieve[p]: sum += p for i in range(p*p, n, p): sieve[i] = False return sum 

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