python - 计算质数

Question

我现在正在做 MIT opencourse 的事情，已经是第二个作业了，我觉得它让我被冷落了。 http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/assignments/pset1a.pdf

具体来说，就是写一个可以计算出第1000个素数的东西。我们只知道 print、==、=、1=、if、else、elif、while、%、-、+、*、/、我认为的命令。我们还不知道导入库。

我的想法是取一个奇数并尝试将其除以 3,4,5,6,7,8,9，如果 %n !=0，则将一个数添加到 NumberofPrimes以 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

看来我来晚了

很简单，如果一个数不能被任何质数整除，那么这个数本身就是一个质数。您可以使用这个事实来最小化划分的数量。

为此，您需要维护一个素数列表。并且对于每个数字，只尝试与列表中已有的素数相除。为了进一步优化它，您可以丢弃所有超过要测试的数字的平方根的素数。您需要为此导入 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]