Лучший алгоритм на простые числа

Question

Я работаю над программой, которая найдет n th. простое число. Например, перечисляя первые шесть простых чисел: 2, 3, 5, 7, 11 и 13, мы можем видеть, что 6-е число - это 13. Я пытаюсь сделать алгоритм, например, если я хочу увидеть 50-е правое, я добавлю 1 к концам функции range(). Я использую этот алгоритм для поиска простых чисел на данный момент;

cnt = 1 
print (2) 
for x in range(3,40,2): 
    div = False 
    for y in range(2,round(x**0.5)+1): 
     if x%y == 0: 
      div = True 
    if div == False: 
     print (x) 
     cnt += 1 

print ("\nThere is {} prime numbers.".format(cnt)) 

Вы видите, что я положил 40. Но я хочу поставить n, так, например, до достижения 50-го числа, добавьте +1 к n. Но это не понравится, если я попробую что-то вроде;

cnt = 1 
n = 40 #example 
while cnt<50: 
    for x in range(3,n,2): 
     #codes 
    if div == False: 
     n += 1 

Я думал, что, когда программа находит простое, это добавит +1 к n и while цикл будет обрабатывать до тех пор пока найти 50 премьер. Но это не так, простые ошибки ошибочны, если я тоже использую этот, ничего соответствующего, что я хочу делать.

• Как сделать этот алгоритм, очевидно, меняя последний элемент range() функции не работает.

• Есть ли лучший/элегантный алгоритм/способ? Если я хочу найти 200.000th prime, мне нужны более быстрые коды.

Редактировать: Сначала я работал со списками, но я постоянно работал с MemoryError при работе с большими числами. Поэтому я передаю это и использую переменную, которая подсчитывает количество простых чисел cnt.

Answer 1

Здесь гораздо более быстрая версия

primes = [] 
primecount = 0 

candidate = 2 
while primecount<50: 
    is_prime = True 
    for prime in primes: 
     if candidate%prime == 0: 
      is_prime = False 
      break 
     elif candidate < prime**2: 
      break 
    if is_prime: 
     primes.append(candidate) 
     primecount += 1 

    candidate += 1 
print primes[-1] 

нота небольшой редактировать добавив тест candidate<prime**2, что OP включен, но я изначально пренебрегли.

Ваш код будет очень медленным по нескольким причинам. Если 2 делит число, которое вы знаете, оно не простое, но вы все еще проверяете, разделяет ли он 3 или 4 или 5 .... Таким образом, вы можете вырваться, как только узнаете, что это не просто. Еще одна серьезная проблема заключается в том, что если 2 не делит число, нет никаких оснований проверять, 4 ли это тоже. Таким образом, вы можете ограничить свое внимание просто проверкой того, попадают ли простые числа перед его делением.

С точки зрения времени выполнения:

Answer 2

Во-первых, для обеспечения обратной совместимости с Python 2, я добавил int() вокруг закругления корня х.

Из того, что я понимаю ваш вопрос, вы ищете что-то вроде этого:

cnt = 1 
maximum=50 #Specify the number you don't want the primes to exceed 
print (2) 
n=20 #highest number 
while cnt<maximum: # 
    for x in range(3,n,2): #using "n" as you hoped 
     div = False 
     for y in range(2,int(round(x**0.5)+1)): 
      if x%y == 0: 
       div = True 
     if div == False: 
      if x<maximum: #we only want to print those up to the maximum 
       print str(x) 
      else: #if it is greater than the maximum, break the for loop 
       break 
      cnt += 1 
    break #break the while loop too. 
print ("\nThere are {} prime numbers.".format(cnt)) 

Это дало мне правильные простые числа. Что касается лучших/более элегантных решений. Если лучше вам нужна скорость, используйте библиотеку с оптимизацией или посмотрите на this для примера быстрой программы. Элегантность субъективна, поэтому я оставлю это в остальной части Интернета.