计算质数

Question

我现在在做麻省理工学院的开放课程，已经到了第二个作业，我感觉自己有点跟不上了。 http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/assignments/pset1a.pdf

这个作业的具体内容是写一个程序，能够计算出第1000个质数。我们目前只知道一些基本的命令，比如打印、==、=、1=、if、else、elif、while、%、-、+、*、/，我觉得就这些。我们还不知道怎么导入库。

我想的实现方法是从一个奇数开始，尝试用3、4、5、6、7、8、9去除它，如果% n不等于0，就在一个叫NumberofPrimes的变量上加1，测试从11开始，给NumberofPrimes一个初始值4。不过我不知道这样做是否正确，因为我不知道怎么显示第1000个质数。

我这样想对吗？

我现在的代码是这样的：

##calculate the 1000th prime number
potprime = 3
numberofprime = 1
cycle = if potprime%3 = 0:
            break
        if potpimre%4 = 0:
            break
        if potprime%5 = 0:
            break
        if potprime%6 = 0:
            break
        if potprime%7 = 0:
            break
        if potprime%8 = 0:
            break
        if potprime%9 = 0:
            break
        numberofprime + 1
        potprime + 1

if potprime%2 == 0:
    potprime = potprime + 1
if potprime != 0:
    cycle

我到底哪里出错了？能不能一步一步教我？我真的很想学，但感觉自己有点被抛在一边了。

在这个时候，看到一个正确的实现方式对我来说会更有帮助，而不是继续这样做。我已经工作了3个小时，但一点进展都没有。如果有人有解决方案，我会很乐意看看，并试着从中学习。

Answer 1

首先，我可以肯定地说，在Python中，如果你想写一个if语句来判断A是否等于B，你需要用==这个符号，而不是=。

其次，你的算法会把143这个数字当作质数，但其实143可以分解成11乘以13。

你需要记录下你已经计算过的所有质数，把它们放到一个数组里。然后用这个数组来判断你正在测试的新数字是否是质数。

Answer 2

下面的代码虽然有点“粗糙”，但因为1000这个数字确实很小，所以它能在几分之一秒内解决你的问题（而且它只用了你目前应该知道的基本知识）：

primesFound = 0
number = 1

while primesFound < 1000:
    number = number + 1          # start from 2

    # test for primality
    divisor = 2
    numberIsPrime = True
    while divisor*divisor <= number:   # while divisor <= sqrt(number)
        if number % divisor == 0:
            numberIsPrime = False
            break
        divisor = divisor + 1

    # found one?
    if numberIsPrime:
        primesFound = primesFound + 1

print number

你可以在这里测试这个解决方案。现在你应该寻找一个更有效的解决办法，进行优化，甚至可以尝试找出第1000000个质数……

Answer 3

看起来我来晚了

其实很简单，如果一个数字不能被任何质数整除，那么这个数字就是质数。你可以利用这个特点来减少除法运算的次数。

为此，你需要保持一个质数的列表。然后对于每个数字，只用列表中的质数来进行除法测试。为了进一步优化，你可以忽略所有大于要测试的数字平方根的质数。你需要导入sqrt()函数来计算平方根。

举个例子，如果你要测试1001，可以尝试用3、5、7、11、13、17、19、23、29和31来测试。这些就足够了。另外，永远不要尝试判断一个偶数是否是质数。所以基本上，如果你测试一个奇数n，接下来就测试下一个数字：(n + 2)

我测试过下面的代码。第1000个质数是7919。其实也不算大数字！！

代码可能是这样的：

from math import sqrt

primeList = [2]
num = 3
isPrime = 1

while len(primeList) < 1000:
    sqrtNum = sqrt(num)

    # test by dividing with only prime numbers
    for primeNumber in primeList:

        # skip testing with prime numbers greater than square root of number
        if num % primeNumber == 0:
            isPrime = 0
            break
        if primeNumber > sqrtNum:
            break

    if isPrime == 1:
        primeList.append(num)
    else:
        isPrime = 1

    #skip even numbers
    num += 2

# print 1000th prime number
print primeList[999]