Project Euler 10. Почему первый код Python работает намного быстрее, чем второй?

Ваш алгоритм проверяет каждое число отдельно от 2 до N (где N = 2000000) на простоту.

Фрагмент-1 использует алгоритм решета Эратосфена, открытый около 2200 г. много лет назад. Он не проверяет каждое число, но:

• Делает "решето" всех чисел от 2 до 2000000.
• Находит первое число (2), помечает его как простое, затем удаляет из сита все его кратные числа.
• Затем находит следующее не удаленное число (3), помечает его как простое и удаляет из сита все его кратные числа.
• Затем находит следующее не удаленное число (5), помечает его как простое и удаляет из сита все его кратные числа.
• ...
• Пока не найдет простое число 1409 и не удалит из сита все его кратные числа.
• Затем все простые числа до 1414 ~= sqrt(2000000) были найдены, и он останавливается.
• Числа от 1415 до 2000000 проверять не нужно. Все они, которые не были удалены, тоже являются простыми.

Таким образом, алгоритм производит все простые числа до N.

Обратите внимание, что он не выполняет никакого деления, только сложения (даже не умножения, и не то, чтобы это имело значение для таких маленьких чисел, но может иметь значение для больших). Временная сложность составляет O(n loglogn), в то время как ваш алгоритм имеет что-то около O(n^(3/2)) (или O(n^(3/2) / logn), как прокомментировал @Daniel Fischer), при условии, что деления стоят так же, как умножения.

Из статьи в Википедии (ссылка выше):

Временная сложность модели машины с произвольным доступом составляет O(n log log n) операций, что является прямым следствием того факта, что ряд простых гармоник асимптотически приближается к log log n.

(с n = 2e6 в этом случае)

Первая версия предварительно вычисляет все простые числа в диапазоне и сохраняет их в массиве sieve, затем найти решение — это просто добавить простые числа в массив. Это можно рассматривать как форму запоминания.

Вторая версия проверяет каждое число в диапазоне, чтобы увидеть, является ли оно простым, повторяя большую работу, уже проделанную предыдущими вычислениями.

В заключение, первая версия избегает повторного вычисления значений, тогда как вторая версия выполняет одни и те же операции снова и снова.

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

В вашем решении число 2 будет проверено на КАЖДОЕ число, когда это число будет проверено на то, что оно является простым. Каждое число, которое вы пройдете по пути, будет использоваться в качестве потенциального делителя для каждого следующего числа.

В первом решении, как только вы перешагнули число, вы никогда не оглядываетесь назад — вы всегда движетесь вперед с места, которого достигли. Кстати, возможная и распространенная оптимизация — использовать нечетные числа только после того, как вы отметили 2:

mark(sieve, 2)
for x in xrange(3, int(len(sieve) ** 0.5) + 1, 2):
    if sieve[x]: mark(sieve, x)

Таким образом, вы просматриваете каждое число только один раз и очищаете все его умножения вперед, а не перебираете все возможные делители снова и снова, проверяя каждое число со всеми его предшественниками, а оператор if не позволяет вам выполнять повторную работу с числом, которое вы встречались ранее.

Как показывает ответ Оскара, ваш алгоритм повторяет большую часть работы. Чтобы увидеть, сколько времени экономит обработка другим алгоритмом, рассмотрите следующую модифицированную версию функций mark() и isprime(), которые отслеживают, сколько раз была вызвана функция, и общее количество итераций цикла for:

calls, count = 0, 0
def mark(sieve, x):
    global calls, count
    calls += 1
    for i in xrange(x+x, len(sieve), x):
        count += 1
        sieve[i] = False

После запуска первого кода с этой новой функцией мы видим, что mark() вызывается 223 раза, всего 4 489 006 (~4,5 миллиона) итераций в цикле for.

calls, count = 0
def isprime(n):
    global calls, count
    calls += 1
    for x in xrange(3, int(n**0.5)+1):
        count += 1
        if n % x == 0:
            return False
    return True

Если мы внесем аналогичные изменения в ваш код, мы увидим, что isprime() вызывается 1 000 000 (1 миллион) раз с 177 492 735 (~ 177,5 миллиона) итераций цикла for.

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