找出第20,第30,第n个素数.(我要20岁但不是30岁？)[Python]

Question

问题是找到第1000个素数.我为此编写了以下python代码.问题是,我得到了10号,20号素数的正确答案,但之后每增加10分,我就得到了一个标记.我无法抓住这里的错误:(

count=1            #to keep count of prime numbers
primes=()          #tuple to hold primes
candidate=3        #variable to test for primes
while count<20:
    for x in range(2,candidate):
        if candidate%x==0:
            candidate=candidate+2
        else : pass
    primes=primes+(candidate,)            
    candidate=candidate+2
    count=count+1
print primes        
print "20th prime is ", primes[-1]

如果您想知道,count初始化为1,因为我没有测试2作为素数(我从3开始)并且candidate正在增加2,因为只有奇数可以是素数.我知道还有其他解决这个问题的方法,比如素数定理,但我想知道这种方法有什么问题.如果您有任何优化,请建议.

谢谢

Answer 1

在test_generators.py中有一个很好的Sieve of Eratosthenes生成器实现:

def intsfrom(i):
     while 1:
         yield i
         i += 1

def firstn(g, n):
     return [g.next() for i in range(n)]

def exclude_multiples(n, ints):
     for i in ints:
         if i % n:
             yield i    

def sieve(ints):
     prime = ints.next()
     yield prime
     not_divisible_by_prime = exclude_multiples(prime, ints)
     for p in sieve(not_divisible_by_prime):
         yield p

primes = sieve(intsfrom(2))

>>> print firstn(primes, 20)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

Answer 2

你的Python代码有很多(!)需要改进,但要回答你的具体问题:

当你找到一个除数(candidate % x == 0)时,你增加候选人,但你没有做任何事情x.这可能会导致两个问题:

1. candidate可能有一个除数,但它比任何x被测试的都小- 因为在循环的下一次迭代中的测试开始时x的值高于x之前的值; 不在2.
2. candidate可能有一个除数,但它比以往任何时候都要大x,因为你x从值开始2到你开始循环时的值candidate.

Answer 3

我不认为这正在测试你认为正在测试的东西。看起来你想说“对于 2 和我的候选人之间的每个数字，检查候选人是否可以被该数字整除”。然而，当你找到一个素数（candidate%x == 0）时，你只是增加了候选者——你仍然需要再次开始你的“for x in ...”循环，因为候选者已经改变了。

这就是我从编写的代码中看到的；当然，这里还有很多其他方法和其他优化可以使用。