Основные номера с использованием генераторов в Python?

Question

Я написал эту простую функцию питона известково:

def isPrime(number): 
    if number == 2: 
     return True 

    elif number > 1 and number % 2 != 0: 
     for current in range(3, number): 
      if number % current == 0: 
       return False 

     return True 

И я звоню его распечатать сумму всех простых чисел от 1 до 2 миллионов, как в проекте euler #10

Однако это ужасно медленно, и мне было интересно, могу ли я решить эту проблему с помощью генераторов? Но я действительно не понимаю генераторов в python полностью.

Любая помощь в том, как решить эту проблему более эффективно будет оценена! Спасибо :)

Answer 1

Во-первых, я предлагаю вам использовать лучшую функцию, чтобы проверить, является ли число простым или нет. Вот лучшая модификация от https://jeffknupp.com/blog/2013/04/07/improve-your-python-yield-and-generators-explained/, которая является отличным объяснением генераторов в Python.

import math 

def is_prime(number): 
    while True: 
     if number == 2: 
      return True 
     elif number > 1 and number % 2 != 0: 
      for current in range(3, int(math.sqrt(number) + 1), 2): 
       if number % current == 0: 
        return False 
      return True 
     return False 

Во-вторых, вам нужно понять, что на самом деле делает генератор. Снова Джефф Кнупп прекрасно объясняет это. Короче говоря, генератор - это функция, которая не «возвращает», просто «дает» и возвращает управление при вызове метода next(). Таким образом, никакие переменные, созданные во время функции, не теряются, а память сохраняется, не создавая переменные, определенные в функции снова и снова.

Тогда вы можете продолжить решение Euler 10, что также объясняется в ссылке. :)

Удачи с остальными Эйлерами!

Answer 2

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

Общая идея заключалась бы в том, чтобы «маркировать» все составные числа (не простые), оставляя позади простые числа. Это довольно эффективно, так как моя реализация python работает в ~ 3.5s