Нахождение n-го числа простых чисел - PullRequest
Новая
       34

Нахождение n-го числа простых чисел

0 голосов
/ 13 июня 2010

Не могу понять, почему это не сработает.Пожалуйста, помогите мне 

from math import sqrt

pN = 0 
numPrimes = 0
num = 1

def checkPrime(x):
   '''Check\'s whether a number is a prime or not'''
   prime = True
   if(x==2):
      prime = True
   elif(x%2==0):
      prime=False
   else:
      root=int(sqrt(x))
      for i in range(3,root,2):
         if(x%i==0):
            prime=False
            break
   return prime

n = int(input("Find n number of primes. N being:"))

while( numPrimes != n ):
   if(  checkPrime( num ) == True ):
      numPrimes += 1
      pN = num
      print("{0}: {1}".format(numPrimes,pN))
   num += 1

print("Prime {0} is: {1}".format(n,pN))

Ответы [ 2 ]

5 голосов
/ 13 июня 2010

Вам нужно изменить 

root=int(sqrt(x))

на 

root=int(sqrt(x))+1

(например, взять 9, int(sqrt(9)) равно 3, range(3, 3, 2) равно [], иВы do действительно хотите проверить деление на 3!).

Технически, 1 тоже не простое число.Добавьте 

if(x<=1):
   prime = False

, и вы получите тот же результат, что и http://www.rsok.com/~jrm/first100primes.html

1 голос
/ 13 июня 2010

В отличие от того, что @Braxton говорит в комментарии, алгоритм Sieve of Eratosthenes можно легко адаптировать для генерации неограниченных простых чисел (например, в качестве потенциально бесконечного генератора, который затем может быть свернут по желанию, например, с помощью itertools.slict).

См. этот рецепт для неограниченного Решета в Python (и обязательно примените улучшения, показанные в комментариях, включая мой ;-) или посмотрите тот же самый рецепт, как окончательно отредактированный для напечатанной Поваренной книги здесь (к сожалению, часть обсуждения в этом хите книг Google урезана, но, по крайней мере, код Решения все есть; -).

...