python - 使用 Python 查找第 n 个素数

Question

当我运行这段代码时，即使只是数到第 10 个素数(而不是 1000)，我也会得到一个偏斜/顶升的输出——我的 is_composite 变量的所有“非素数”标题，我的 test_num 给了我素数和合数，我的 prime_count 已关闭

开发人员共享的一些答案使用函数和数学导入——这是我们尚未涵盖的内容。我不是想得到最有效的答案；我只是想编写可行的 Python 代码来理解循环的基础知识。

---

  # test a prime by diving number by previous sequence of number(s) (% == 0).  Do this by
  # counting up from 1 all the way to 1000.

test_num = 2 #these are the numbers that are being tested for primality
is_composite = 'not prime' # will be counted by prime_count
prime_count = 0 #count the number of primes


while (prime_count<10): #counts number primes and make sures that loop stops after the 1000th prime (here: I am just running it to the tenth for quick testing)


 test_num = test_num + 1   # starts with two, tested for primality and counted if so
 x = test_num - 1  #denominator for prime equation

 while (x>2):   
  if test_num%(x) == 0:
   is_composite = 'not prime'
  else: 
   prime_count = prime_count + 1 
  x = x - 1 


  print is_composite
  print test_num
  print prime_count 

Answer 1

查看MIT给出的提示为你的任务。我在下面引用它们:

1. 初始化一些状态变量

2. 生成所有大于 1 的(奇数)整数作为素数候选

3. 对每个候选整数，检验它是否为素数

   3.1。一种简单的方法是测试是否有任何其他 > 1 的整数均分候选者，余数为 0。为此，您可以使用模运算，例如，表达式 a%b 返回整数 a 除以整数 b 后的余数。

   3.2。您可能会考虑需要检查哪些整数作为除数——当然您不需要超出您正在检查的候选项，但是您多久可以停止检查？

   <

4. 如果候选者是素数，打印出一些信息以便您知道您在计算中的位置，并更新状态变量

5. 当您达到某个适当的结束条件时停止。在制定此条件时，不要忘记您的程序没有生成第一个素数 (2)。

它可能看起来像这样:

def primes(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
    return [2] + [i for i in xrange(3,n,2) if sieve[i]]