计算质数

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个素数的东西。我们只知道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]

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

您可以测试解决方案here。现在你应该找到一个更有效的解决方案，优化，也许去1000000次素数...

Answer 3

首先，我非常确定在Python语言中，如果你想有一个if语句来测试A = B，你需要使用==操作符，而不是=。

另一方面，您的算法会将数字143视为质数，即使143 = 11 * 13

您需要跟踪您已经计算的所有质数-将它们添加到一个数组中。使用该数组来确定您正在测试的新数字是否为质数。