Оптимизация кода простого числа

Question

Это мой код в python для вычисления суммы простых чисел, меньших заданного числа.
Что еще я могу сделать, чтобы оптимизировать его?

import math
primes = [2,]                      #primes store the prime numbers



for i in xrange(3,20000,2):                    #i is the test number
    x = math.sqrt(i)
    isprime = True
    for j in primes:               #j is the devider. only primes are used as deviders
        if j <= x:
            if i%j == 0:
                    isprime = False
                    break


    if isprime:
        primes.append(i,)


print sum (primes,)

Answer 1

Вы можете использовать другой алгоритм, называемый Сито Эратосфена , который будет быстрее, но займет больше памяти.Сохраните массив флагов, показывающих, является ли каждое число простым или нет, и для каждого нового простого установите его равным нулю для всех кратных этого простого числа.если вы используете эффективный битовый массив, такой как в этом примере (прокрутите страницу вниз, и вы найдете пример Sieve of Eratosthenes).

Answer 2

Еще одна вещь, которую вы могли бы оптимизировать, это переместить вычисление sqrt за пределы внутреннего цикла.В конце концов, i остается постоянным, поэтому нет необходимости каждый раз пересчитывать sqrt(i).

Answer 3

primes = primes + (i,) очень дорого.Он копирует каждый элемент на каждом проходе цикла, превращая ваше элегантное решение для динамического программирования в алгоритм O (N ² ).Вместо этого используйте списки:

primes = [2]
...
    primes.append(i)

Кроме того, выйдите из цикла рано после прохождения sqrt (i).И, поскольку вы гарантированно передаете sqrt (i) перед запуском конца списка простых чисел, обновите список на месте, а не храните isprime для последующего использования:

...
if j > math.sqrt(i):
    primes.append(i)
    break
if i%j == 0:
    break
...

Наконец,хотя это не имеет ничего общего с производительностью, более Pythonic использует диапазон вместо while:

for i in range(3, 10000, 2):
    ...

Answer 4

Просто другой код без использования импорта:

#This will check n, if it is prime, it will return n, if not, it will return 0
def get_primes(n):
    if n < 2:
        return 0
    i = 2
    while True:
        if i * i > n:
            return n
        if n % i == 0:
            return 0
        i += 1

#this will sum up every prime number up to n
def sum_primes(n):
    if n < 2:
        return 0
    i, s = 2, 0
    while i < n:
        s += get_primes(i)
        i += 1
    return s

n = 1000000
print sum_primes(n)

Answer 5

РЕДАКТИРОВАТЬ: убрал некоторую глупость, находясь под влиянием

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