Подведение больших простых чисел требует времени! Как я могу сделать это более эффективным? - PullRequest
Новая
       32

Подведение больших простых чисел требует времени! Как я могу сделать это более эффективным?

1 голос
/ 09 июля 2019

Я пытаюсь завершить Десятую задачу Project Euler , но код, который у меня сейчас есть, занимает так много времени, что он не смог выполнить.

Я оглянулся, но не смог выяснить, как заставить код работать быстрее.

У меня есть код: 

def IsPrime(num):
    for i in range(2, num/2):
        if num % i == 0:
            prime = False
            return prime
    prime = True
    return prime

def SumOfPrime(limit):
    primesum=2+3    #For some reason my prime finder doesn't allow numbers below 5
    for check in range(5,limit):
        prime=IsPrime(check)
        if prime == True:
            primesum += check
    return primesum^2

print(SumOfPrime(2000000))

Правильный ответ должен быть 142913828922, однако, как уже упоминалось ранее, я не получаю вывод полностью. Есть ли способ сделать этот код быстрее?

Ответы [ 3 ]

0 голосов
/ 09 июля 2019

теперь для его завершения требуется 32,98 сек. Я хотел бы увидеть быстрее Алгоритм

Вы должны использовать Сито Эратосфена . Игнорируя это, эта переделка должна занять меньше 10 секунд: 

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

    if number % 2 == 0:
        return False

    for divisor in range(3, int(number ** 0.5) + 1, 2):
        if number % divisor == 0:
            return False

    return True

def sumOfPrimes(limit):
    return sum(number for number in range(limit) if isPrime(number))

print(sumOfPrimes(2000000))

Обрабатывать четные числа как особый случай в isPrime(), а затем просто иметь дело с нечетными делителями. Использование понимания или выражения генератора опускает больше вашего зацикленного кода до уровня C и обычно дает вам немного большую скорость.

0 голосов
/ 09 июля 2019

Используйте сито Эратосфена: 

$ python
Python 2.7.13 (default, Mar 13 2017, 20:56:15)
[GCC 5.4.0] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> def sumPrimes(n):
...     i, p, ps, m, sum = 0, 3, [2], n // 2, 2
...     sieve = [True] * m
...     while p <= n:
...         if sieve[i]:
...             sum += p
...             for j in range((p*p-3)/2, m, p):
...                 sieve[j] = False
...         i, p = i+1, p+2
...     return sum
...
>>> from time import time
>>> start = time(); print sumPrimes(2000000); print time() - start
142913828922
0.262000083923

Около четверти секунды на моей машине.

0 голосов
/ 09 июля 2019

Несколько советов по ускорению вашей реализации:

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

Если вы хотите более эффективный алгоритм, пожалуйста, проверьте https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

...