找出第 20、30、n 个质数.(我第 20 名但不是第 30 名?)[Python] [英] Find out 20th, 30th, nth prime number. (I'm getting 20th but not 30th?) [Python]
问题描述
问题是找到第 1000 个质数.我为此编写了以下python代码.问题是,我得到了第 10 次、第 20 次质数的正确答案,但之后每增加 10 次就会让我偏离目标.我在这里找不到错误:(
The question is to find the 1000th prime number. I wrote the following python code for this. The problem is, I get the right answer for the 10th , 20th prime but after that each increment of 10 leaves me one off the mark. I can't catch the bug here :(
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,因为只有奇数可以是素数.我知道还有其他方法可以解决这个问题,例如素数定理,但我想知道这种方法有什么问题.此外,如果您有任何优化建议,请提出建议.
In case you're wondering, count is initialised as 1 because I am not testing for 2 as a prime number(I'm starting from 3) and candidate
is being incremented by 2 because only odd numbers can be prime numbers. I know there are other ways of solving this problem, such as the prime number theorem but I wanna know what's wrong with this approach. Also if there are any optimisations you have in mind, please suggest.
谢谢
推荐答案
有一个很好的 Eratosthenes 的筛子 test_generators.py 中的生成器实现:
There is a nice Sieve of Eratosthenes generator implementation in test_generators.py:
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]
这篇关于找出第 20、30、n 个质数.(我第 20 名但不是第 30 名?)[Python]的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!