使用python查找第1000个素数时出错

Question

我正在麻省理工学院开放的课件网站上自学Python。我很难仅仅利用在讲座中学到的信息来完成这项作业。我学到的最后一件事是使用"While“和"For”循环进行迭代。我还没学会函数。是否有可能只使用这个来编写计算和打印第1000个素数的程序？

到目前为止，我的代码如下：

count = 0
prime = []
candidate = []
x = 2
y = 1
while count < 1000:
    x = x+1
    if x > 1:
        if x%2 != 0:
            if x%3 != 0:
                if x%5 != 0:
                    if x%7 != 0:
                        if x%11 != 0:
                            if x%13 != 0:
                                candidate.append(x)

Answer 1

您的代码有一些问题，我将尝试指出：

count = 0
prime = []          # this is obviously meant to collect all primes
candidate = []      # what is this supposed to do then though?
x = 2
y = 1               # never used
while count < 1000: # you start at `count = 0` but never increase the count
                    # later on, so would loop forever
    x = x+1
    if x > 1: # x is always bigger than 1 because you started at 2
              # and only increase it; also, you skipped 2 itself
        if x%2 != 0:                      # here, all you do is check if the
            if x%3 != 0:                  # number is dividable by any prime you
                if x%5 != 0:              # know of
                    if x%7 != 0:          # you can easily make this check work
                        if x%11 != 0:     # for any set (or list) of primes
                            if x%13 != 0: #
                                candidate.append(x) # why a candidate? If it’s
                                                    # not dividable by all primes
                                                    # it’s a prime itself

因此，在此基础上，您可以使所有的工作：

primes = [2] # we're going to start with 2 directly
count = 1    # and we have already one; `2`
x = 2
while count < 1000:
    x += 1
    isPrime = True          # assume it’s a prime
    for p in primes:        # check for every prime
        if x % p == 0:      # if it’s a divisor of the number
            isPrime = False # then x is definitely not a prime
            break           # so we can stop this loop directly

    if isPrime:             # if it’s still a prime after looping
        primes.append(x)    # then it’s a prime too, so store it
        count += 1          # and don’t forget to increase the count

for循环中的p来自哪里？

for x in something是一个结构，它将遍历something中的每个元素，对于每次迭代，它都会为您提供一个包含当前值的变量x。例如，下面将分别打印1、2、3。

for i in [1, 2, 3]:
    print(i)

或者对于一个素数列表，for p in primes将遍历所有存储的素数，并且在每次迭代中，p将是列表中的一个素数。

所以，整个检查基本上会循环到每个已知的素数上，对于每个素数，它将检查所述素数是否是这个数的除数。如果我们找到这样的一个素数，我们可以中止循环，因为当前的数字绝对不是素数本身。

Answer 2

没有为您做所有的事情，正如已经说过的那样，您正在prime中建立一个素数列表，这样您就可以使用它而不是硬编码的东西来检查。

 prime = []
 x = 2
 while len(prime) < 1000:
     if *** check here ***
        prime.append(x)
     x = x + 1

Answer 3

import time    
start = time.time()

primes = [2,]  # Initial list of primes
l = 1  # No in the list
n = 3  # First candidate
while l < 10000:  # Target No
    Ok = True  # Assume it is
    for p in primes[1:1+l//2]:  # Check all in the first half of the list 
       if (n % p) == 0:  # Divides exactly
           Ok = False    # So not prime
           break         # Skip the rest
    if Ok:  # It was a prime
       primes.append(n)  # Add it
       l += 1            # and the count
       #print n
    n += 2  # Next non-even number
end = time.time()
print primes[-1]
print 'took', end-start