Euler Project, # 7 - Python

Question

Итак, я пытаюсь найти 10 001st prime #. Вот мой код -

counter = 3 
primes = [1] 

while len(primes) < 10002: 
    for i in range(2, counter): 
     if counter % i == 0: 
      counter += 1 
    else: 
     primes.append(counter) 
     counter += 1 

print counter 

Так что я получаю, как выход в штрихах список чисел, первые цифры 1, 3, 5, 7, 11 ... до сих пор, так хорошо .. 13, 17, 19, 23, 27 ... подождите, 27? Таким образом, в этот момент он ломается и начинает возвращаться в основном простые числа, но не все простые числа. И это длится вечно.

Я новичок в программировании, прошел через курс Python CodeAcademy и теперь пытаюсь понять, как пройти мимо того, что было в основном просто введением в грамматику. Я не прихожу из математического фона, поэтому, хотя я знаю, что такое премьер, я знаю, что есть намного лучшие способы сделать это. Если в подобной лодке кто-то хочет «наладить партнерство» и работать вместе над изучением Py2.7, я более чем счастлив.

Answer 1

Я ничего не сделаю для вас, потому что именно поэтому вы делаете Project Euler, но я укажу вам в направлении The Sieve of Eratosthenes. Он вычислит в секундах, что ваш код будет делать в часах.

Он работает так: (в псевдокоде)

for known_prime in a huge list of numbers: 
    k=2 
    while known_prime*k < the biggest number: 
     known_prime*k is not prime 
     k += 1 

После того, как вы сделали это через SQRT из списка, вы нашли каждое простое число в списке.

Answer 2

Поскольку вы делаете загадку Эйлера проекта, вам явно нужны комментарии к вашему коду, а не к решению.

Ваш код:

counter = 3 
primes = [1] 

while len(primes) < 10002: 
    for i in range(2, counter): 
     if counter % i == 0: 
      counter += 1 
    else: # Mis-aligned else (assuming it's intended for the if) 
     primes.append(counter) 
     counter += 1 

print counter 

1. Вашего else является неправильно выровненным с if
2. Вашего for петли проходит весь путь к counter и тестированию делимости на себя обязана найти остаток 0.
3. Ваше предложение else будет касаться каждого нефактора counter. Большинство чисел не будет фактором, поэтому вы не хотите принимать меры в этом случае. Вместо этого выходите из цикла, когда запускается часть if.
4. После выхода из цикла for вы хотите проверить, был ли найден фактор, а если нет, добавьте counter в список простых чисел.

Похоже, вы пытаетесь реализовать наивный неуправляемый поиск грубой силы, и это нормально.

Возможно, попробуйте и запишите алгоритм в словах или псевдокоде перед его кодировкой.

Answer 3

В качестве упражнения для вас, вместо простого написания для вас простого пошагового кода, я напишу сложную строку кода с решением аналогичной проблемы.

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

def primes(n): 
    return sorted(set(range(2, n+1)) - set([p*i for p in range(2, n+1) for i in range(p, n+1)])) 

Answer 4

Если вы хотите, чтобы написать эффективный и смарт-код, вы можете использовать Решето Эратосфена, хороший алгоритм нахождение простых чисел в заданном диапазоне. Для получения дополнительной информации прочитайте: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes