Project Euler # 10 (Python)

Question

Почему мой алгоритм для нахождения суммы всех простых чисел ниже 2 миллионов так медленно? Я довольно начинающий программист и это то, что я придумал для нахождения решения:

import time 

sum = 2 
start = time.time() 

for number in range(3, 2000000): 
    prime = True 
    for x in range(2, number): 
     if number % x == 0: 
      prime = False 
    if prime: 
     sum += number 

print "Sum =", sum 
end = time.time() - start 
print "Runtime =", end 

Может кто-то пожалуйста, помогите мне? Спасибо!

Answer 1

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

Нечто подобное работает быстрее, но не в коем случае не оптимален:

value=2 
    for i in range(3, 2000000): 
     prime=True 
     if i%2 != 0: 
      for j in range(3, int(round(sqrt(i)+1)),2): 
       if i % j==0: 
        prime=False 
     else: 
      prime=False 
     if prime==True: 
      value+=i 
    print value 

Answer 2

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

Взгляните на сито Аткина (и родственные сита) (http://en.wikipedia.org/wiki/Sieve_of_Atkin), чтобы понять, как ускорить первое поколение сверх грубой силы (алгоритмически то есть).

Затем взгляните на удивительный ответ на этот S.O.-post (Fastest way to list all primes below N), который синхронизирует несколько алгоритмов/реализаций первого поколения.

Answer 3

Вам необходимо использовать сито для просеивания сита eratostheneses и попытаться реализовать его в коде.

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

Answer 4

Никто не указал на это, но используя range в Python 2.x очень медленно. Используйте xrange instaed, в этом случае это должно дать вам огромное преимущество в производительности.
См this question.

Кроме того, вы не должны циклически, пока число проверив, не проверяя, пока round(sqrt(n)) + 1 не достаточно. (Если число, большее, чем его квадрат, делит его, число меньше квадрата, которое вы, должно быть, уже заметили.)

Answer 5

Ваш алгоритм использует пробное деление, которое очень медленно. В лучшем алгоритме используется сито эратосфенов:

def sumPrimes(n): 
    sum, sieve = 0, [True] * n 
    for p in range(2, n): 
     if sieve[p]: 
      sum += p 
      for i in range(p*p, n, p): 
       sieve[i] = False 
    return sum 

print sumPrimes(2000000) 

Это должно работать менее чем за секунду. Если вы заинтересованы в программировании с помощью простых чисел, я скромно рекомендую этот essay в моем блоге.

Answer 6

Этот вопрос дает результат очень быстро, когда вы используете сито из eratosthenes Link to it. Вы можете сделать это еще быстрее с небольшими изменениями, такими как итерирование всего 2 миллионов номеров всего в полтора раза, учитывая только нечетные числа. Таким образом, вы можете сэкономить много времени.

n = 2000000 
ar = [False for x in range(n)] 
sum = 2 
def mul(a): 
    i = 2;p = i*a 
    while (p < n): 
     ar[p] = 1 
     ++i 
     p = i*a 
while (x < n): 
    if(ar[x] == 0): 
     sum += x;mul(x) 
    x += 2 
print (sum) 

Здесь вы можете увидеть один и тот же алгоритм в C++: -

#include<bits/stdc++.h> 
using namespace std; 
const int n = 2000000; 
bool ar[n]; 
void mul(int a) 
{ 
    int i = 2;int p = i*a; 
    while(p < n) 
    { 
     ar[p] = 1; 
     ++i;p = i*a; 
    } 
} 
long long sieve() 
{ 
    long long sum = 2; 
    for(int i = 3;i < n;i += 2) 
    { 
     if(ar[i] == 0) 
      sum += i,mul(i); 
    } 
    return sum; 
} 
int main() 
{ 
    cout<<sieve(); 
    return 0; 
} 

C++ работает около 10 раз быстрее, чем питон в любом случае, и для этого алгоритма тоже.

Answer 7

sum = 2 

def isPrime(n): 
    if n % 2 == 0: return False 
    for i in range(3, int(n**0.5)+1, 2): 
     if n % i == 0: return False 
    return True 
if __name__ == "__main__": 
    n = 1 
    while n < 2000000: 
     n += 2 
     if isPrime(n):sum += n 
print sum 

Answer 8

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

• Есть функция, которая дает вам следующее простое число и временно возвращает управление вызывающему. Такие функции известны как GENERATORS.
• Для определения функции генератора используйте команду yield вместо return.
• Когда вы используете генераторы, это похоже на то, что функция будет вызвана снова, и когда это произойдет, выполнение внутри функции продолжается сразу после команды yield вместо того, чтобы снова перебирать всю функцию.
• Преимущество этого подхода заключается в том, что при длительном запуске итератора вы избегаете потребления всей памяти системы.

Я рекомендую вам взглянуть на this article about generators in python. Это дает более подробное объяснение этого примера.

решение было бы что-то вроде этого:

import math 

# Check if a number is prime 
def is_prime(number): 
    if number > 1: 
     if number == 2: 
      return True 
     if number % 2 == 0: 
      return False 
     for current in range(3, int(math.sqrt(number) + 1), 2): 
      if number % current == 0: 
       return False 
     return True 
    return False 

# Get the next after a given number 
def get_primes(number): 
    while True: 
     if is_prime(number): 
      yield number 
     # Next call to the function will continue here! 
     number += 1 

# Get the sum of all prime numbers under a number 
def sum_primes_under(limit): 
    total = 2 
    for next_prime in get_primes(3): 
     if next_prime < limit: 
      total += next_prime 
     else: 
      print(total) 
      return 

# Call the function 
sum_primes_under(2000000)