Как я могу заставить Python работать быстрее?

Question

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

Но похоже, что это происходит навсегда. Как я могу ускорить этот код?

def find_primes(n): 
    "Find the prime numbers below n" 
    primes=[]; 
    for i in range(2,n): 
     for fac in range (2,i): 
      if i!=fac and i%fac == 0: 
       break 
     else: 
      primes.append(i) 
    return primes 

def add_primes(m): 
    "Sum all the prime numbers below m" 
    newlist=find_primes(m); 
    t=sum(newlist); 
    return t 

PS: Я вроде послушника о Python, так что я буду рад, если вы можете хорошо объяснить свои ошибки. Заранее спасибо.

Answer 1

Внесите Sieve of Eratosthenes. Это заставит ваш код работать намного меньше, чем сейчас, делая его намного быстрее.

Answer 2

Вы можете улучшить свой текущий код, заменив на fac in range (2,i) соответствии с этим:

for fac in primes: 

код:

def find_primes1(n): 
    "Find the prime numbers below n" 
    primes=[2,3]  #initialize primes with 2 values 
    for i in range(4,n): 
     for fac in primes: 
      if i!=fac and i%fac == 0: 
       break 
     else: 
      primes.append(i) 
    return primes 

Временные сравнения:

In [6]: %timeit find_primes(10**4) # your version 
1 loops, best of 3: 2.33 s per loop 

In [7]: %timeit find_primes1(10**4) 
1 loops, best of 3: 171 ms per loop 

In [8]: find_primes1(10**3)==find_primes(10**3) 
Out[8]: True 

Но для больших значений, должен определенно узнать метод Sieve of Eratosthenes.