Медленная оптимизация поиска Python Prime

У меня есть 2 версии кода. Оба ищут все простые числа ниже определенного потолочного значения.

Первый — это проверка по набору всех нечетных чисел. Второй в тестировании против набора всех 6к-1 и 6к + 1.

По идее, вторая версия должна быть быстрее первой. Однако результат говорит об обратном.

Для менее 1 миллиона человек первый работает за 1,477835 секунды, а второй — за 1,521462 секунды.

Для менее чем 10 миллионов человек первый работает в течение 30,929565 секунд, а второй — 32,825142 секунды.

Я не тестировал их на другой машине.

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

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

Может быть, из-за того, что у меня больше вложенных циклов? Или дело в доступе к памяти? Может быть, это причуда питона, когда важны детали реализации? Может быть, в каком-то смысле первая версия проще и, следовательно, может быть лучше оптимизирована с помощью python по сравнению со второй?

Если бы кто-то мог дать некоторые объяснения, предложения, даже решения или альтернативы, это было бы очень полезно.

#!/usr/bin/env python3.8

import sys
import time
import math

if len(sys.argv) != 2:
    print('usage:')
    print('    (ceiling)')
    print('        Find primes less than ceiling.')
    sys.exit(-1)

try:
    ceiling = int(sys.argv[1])
except:
    print('Fail to parse ceiling ({}) as integer.'.format(sys.argv[1]))
    sys.exit(-2)

if ceiling < 3:
    print('Minimum ceiling value is 3.')
    sys.exit(-3)

prime = [3]

# start benchmark
bench_start = time.perf_counter()

# range(start, end, step) does not include end
# step = 2 to avoid checking even numbers
for i in range(5, ceiling + 1, 2):
    # test only against factors less than the square root
    root = math.sqrt(i)
    for j in prime:
        if j > root:
            prime.append(i)
            break
        if i % j == 0:
            break

# end of benchmark
bench_end = time.perf_counter()

# prepend 2 to the prime list since it was skipped
prime.insert(0, 2)

print(prime)
print('Number of, primes less than {0}, found: {1}'.format(ceiling, len(prime)))

# benchmark report
print('Time elapsed: {:f}s'.format(bench_end - bench_start))

sys.exit(0)

#!/usr/bin/env python3.8

import sys
import time
import math

if len(sys.argv) != 2:
    print('usage:')
    print('    (ceiling)')
    print('        Find primes less than or equal to ceiling.')
    sys.exit(-1)

try:
    ceiling = int(sys.argv[1])
except:
    print('Fail to parse ceiling ({}) as integer.'.format(sys.argv[1]))
    sys.exit(-2)

if ceiling < 3:
    print('Minimum ceiling value is 3.')
    sys.exit(-3)

prime = [3]

# start benchmark
bench_start = time.perf_counter()

# range(start, end, step) does not include end
# test only for 6k-1 and 6k+1
# use (ceiling+1)+1 in case of ceiling = 6k-1
for h in range(6, ceiling+2, 6):
    for i in [h-1, h+1]:
        # test only against factors less than the square root
        root = math.sqrt(i)
        for j in prime:
            if j > root:
                prime.append(i)
                break
            if i % j == 0:
                break

# end of benchmark
bench_end = time.perf_counter()

# when ceiling = {6k-1, 6k}, remove 6k+1
if prime[-1] > ceiling:
    prime.pop()

# prepend 2 to the prime list since it was skipped
prime.insert(0, 2)

print(prime)
print('Number of, primes less than or equal to {0}, found: {1}'.format(ceiling, len(prime)))

# benchmark report
print('Time elapsed: {:f}s'.format(bench_end-bench_start))

sys.exit(0)
```

Разница в среднем составляет 0,2 микросекунды на каждое проверяемое число.

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

...
for i in range(5, ceiling+1, 6):
    # test only against factors less than the square root
    # just use the sqrt of the bigger number to avoid another call to sqrt
    root = math.sqrt(i + 2)

    # tests 6k - 1
    for j in prime:
        if j > root:
            prime.append(i)
            break
        if i % j == 0:
            break

    # tests 6k + 1
    i += 2
    for j in prime:
        if j > root:
            prime.append(i)
            break
        if i % j == 0:
            break
    ...