计算素数

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]