Проект Эйлера 357 простое число генераторов в Python 3


Я перебирая на проект Эйлера 357 , поскольку нет лучшего алгоритм приходит в голову. Задача спрашивает:

Найти сумму всех натуральных чисел п , не превышающий 108 такая, что для каждого делителя д о н, д+н/д премьер.

Код такой:

#!/bin/env python3

import time 
import math

"""
https://projecteuler.net/problem=357

"""

start = time.time()


def primes(ubound=10**5):
    """ Generating prime numbers LIST
        https://stackoverflow.com/a/8627193/1770460
    """
    size = (ubound - 3) // 2
    a = [False] * size
    s = 0
    primes = []
    while s < size:
        t = 2 * s
        p = t + 3
        primes.append(p)
        for n in range(t * (s + 3) + 3, size, p):
            a[n] = True
        s = s + 1
        while s < size and a[s]:
            s = s + 1
    return primes

the_primes = primes()

def number_divisors(max_limit=10**5):
    """ Find the divisors of every number.
        Return it in a dict in the format: 
        { number1: [divisor1, divisor2 ... ], .. }
    """
    num_divs = {}
    for i in range(4, max_limit): 
        if i in the_primes:
            continue
        else:
            sq = math.sqrt(i)
            for n in range(2, int(sq) + 1):
                if i not in num_divs:
                    num_divs[i] = [1]
                if i % n == 0:
                    if n == i / n:
                        num_divs[i].append(n)
                    else:
                        num_divs[i].extend((n, i / n))
    return num_divs



def find_count(d):
    """ Check every number whether the divisors i.e. d + number / d is 
        prime. 
    """
    assert d is not None

    count = 0
    for number, list_divisors in d.items():
        all_primes = True
        for each_div in list_divisors:
            val = (each_div + (number / each_div))
            if val not in the_primes:
                all_primes = False
                break
        if all_primes:
            count += 1 
    return count




if __name__ == '__main__':

    num_divisors = number_divisors()
    print(find_count(num_divisors))

    elapsed_time = (time.time() - start)
    print('time elapsed %s sec.' % elapsed_time)

Профилирование сценарий показывает, что find_count первое узкое место и по советам других ответов значения должны быть кэшированы(?) почему-то.

$ python3 -m cProfile 357.py                                      
275
time elapsed 167.41558241844177 sec.
         583580 function calls in 167.416 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000  167.416  167.416 357.py:3(<module>)
        1    0.020    0.020    0.020    0.020 357.py:30(primes)
        1   24.526   24.526   24.740   24.740 357.py:51(number_divisors)
        1  142.655  142.655  142.655  142.655 357.py:75(find_count)

Любые советы о том, как улучшить find_count()?



Комментарии
2 ответа

Самое очевидное улучшение-заметить, что if i in the_primes и if val not in the_primes Как взять \$\mathcal{о}(н)\$ времени. Если вы сделали the_primes а set вместо list это было бы \$\mathcal{О}(1)\$. Поэтому просто напишу:

the_primes = set(primes())

Также обратите внимание, что ваш "генератор простых чисел" на самом деле не генератор на Python. Для этого вам нужно добавить yield:

def primes(ubound=10**5):
""" Generating prime numbers https://stackoverflow.com/a/8627193/1770460 """
size = (ubound - 3) // 2
a = [False] * size
s = 0
while s < size:
t = 2 * s
p = t + 3
yield p
for n in range(t * (s + 3) + 3, size, p):
a[n] = True
s = s + 1
while s < size and a[s]:
s = s + 1

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


Ваш исходный код занимает около 43.5 s на моей машине. С двумя пересадками в этом посте этом падает до менее 1,7 с:

$ python3 -m cProfile 357.py
275
time elapsed 1.6228196620941162 sec.
583585 function calls in 1.623 seconds

Ordered by: standard name

ncalls tottime percall cumtime percall filename:lineno(function)
...
9592 0.011 0.000 0.011 0.000 euler_357.py:14(primes)
1 0.001 0.001 1.623 1.623 euler_357.py:3(<module>)
1 1.524 1.524 1.584 1.584 euler_357.py:34(number_divisors)
1 0.026 0.026 0.026 0.026 euler_357.py:56(find_count)
...

2
ответ дан 24 февраля 2018 в 09:02 Источник Поделиться

Это стоит делать немного математики до начала перебором. Для того, чтобы не испортить проблемы, я дам пару подсказок.

Подсказка 1


Если \ФП\$ удовлетворяет условию задачи, то за каждый делитель \$д\ долларов \ФП\$, это должно быть так, что \$Д + {П\По д}\$ - простое. Есть ли делители \н$\$, что уже знаешь (без разложения на множители \Н$\$)? Таким образом, можно сделать вывод о \ФП\$?

Подсказка 2


Если \ФП\$ удовлетворяет условию задачи, может ли быть так, что \N $\$ имеет неоднократные фактор? То есть, может ли быть премьер \$Р\$ такие, что$п^2\$ делит \ФП\$?

1
ответ дан 25 февраля 2018 в 02:02 Источник Поделиться