Задача из проекта Эйлера #7 в Python (10001st простое число)


Мне удалось решить 7-й проект Эйлера проблемы, однако я думаю, что это может быть улучшено много, я не профессиональный программист или даже считать себя действительно хорошо. Какие-либо улучшения / предложения будут очень полезны.

Постановка задачи:

Путем перечисления первые шесть простых чисел: 2, 3, 5, 7, 11, и 13, мы видим, что 6-го премьер-это 13.

Что такое 10 001st простое число?

Это мое решение.

counter = 2
n = 10001
for i in range(3, 1000000, 2):
 k = 1
 while k < i:
  k += 2
  if i % k == 0:
   break
  if k + 2 == i:
   counter += 1
  if counter == n:
   print(i)
   raise ZeroDivisionError

Программа пропустить 2 и 3, в мою попытку сделать это быстрее. В конце я поднимаю ошибка для того, чтобы остановить программу от зацикливания.



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

Что мне не нравится ваше решение является неоправданно большое количество сложности вашего кода, что отрицательно сказывается на его производительности.

Когда я решил эту проблему сам, я использовал решето Эратосфена для генерации списка простых чисел вплоть до произвольного предела (я тоже выбрал миллион, но вы могли бы использовать формулу , чтобы вычислить его) и индексируются, что список на 10 000, чтобы получить 10,001-го номера.

Вот как я реализовал решето:

def primes_upto(limit):
limitN = limit+1
not_prime = set()
primes = [2]

for i in range(3, limitN, 2):
if i in not_prime:
continue

for j in range(i*3, limitN, i*2):
not_prime.add(j)

primes.append(i)
return primes

Как вы можете видеть, этот подход уменьшает сложность кода. Кроме того, это примерно на 28 секунд быстрее, чем ваш подход.

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

Я не собираюсь обращать внимание на ваш алгоритм, как Arnav является прямо там, но вместо того, чтобы сосредоточиться на проблемах стиля. Это должен быть гигантский красный флаг, когда вы поднять ZeroDivisionError когда вы не деление на ноль. Правильное решение здесь-поставить свой код внутри функции, которая позволит вам вернуть правильный результат. Находясь здесь, вы могли бы также сделать верхний предел вашего диапазона n*n вместо 1,000,000, который позволит его работать для больших значений. Кроме того, я знаю, я сказал, что я бы не зацикливался на алгоритм, но вы можете сделать внутренний контур while k*k<iкак какого-то фактора n будет меньше n**.5. Это простое изменение делает ваш код взять .1 секунду вместо 30.

def nth_prime(n):
counter = 2
for i in range(3, n**2, 2):
k = 1
while k*k < i:
k += 2
if i % k == 0:
break
else:
counter += 1
if counter == n:
return i

print(nth_prime(100001))

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

Верхняя граница ценность

Есть известная верхняя граница для n-го премьер.

Это означает, что вам не нужно, чтобы догадаться, насколько велика она может быть. upper_bound_for_p_n(10001) говорит нам меньше, чем за микросекунду, что нужное количество не может быть больше 114320.

Вам просто нужно применить решето Erathosthenes до 114320, а вы закончите:

from math import log, ceil

def find_primes(limit):
nums = [True] * (limit + 1)
nums[0] = nums[1] = False

for (i, is_prime) in enumerate(nums):
if is_prime:
yield i
for n in range(i * i, limit + 1, i):
nums[n] = False

def upper_bound_for_p_n(n):
if n < 6:
return 100
return ceil(n * (log(n) + log(log(n))))

def find_n_prime(n):
primes = list(find_primes(upper_bound_for_p_n(n)))
return primes[n - 1]

Он вычисляет 10001th Prime в 15мс на моем компьютере, по сравнению с 35С для вашего кода.

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

Один из способов решить эту проблему и эффективно использовать память с помощью генераторов, таким образом, только один премьер в то время обрабатывается, и вы не выходите из памяти

def is_prime(n):
if n == 2:
return True
if n % 2 == 0 or n < 2:
return False
limit = int(n ** 0.5) + 1
for i in range(3, limit, 2):
if n % i == 0:
return False
return True

def next_prime(count_limit):
yield 2
count = 1
n = 3
while True:
if is_prime(n):
yield n
count += 1
if count == count_limit:
return
n += 2

n = 10001

# Good
item = None
for item in next_prime(n):
pass
print(item)

# Better
from collections import deque
dd = deque(next_prime(n), maxlen=1)
print(dd.pop())

Кроме того, если вам нужно, чтобы запустить его несколько раз, мемоизация предложил:

def memoize(f):
memo = {}
def helper(x):
if x not in memo:
memo[x] = f(x)
return memo[x]
return helper

@memoize
def is_prime(n):
...

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