1

我已经决定是时候开始学习编码了。我对 HTML 和 CSS 有一些了解，但我希望能够为 iOS 开发。我知道我还有很长的路要走，但我的目标是一步一步地到达那里。

我正在完成 iTunes U 上的 MIT Python 课程，但我一直在做作业。我理解枚举和测试每一个可能的结果以找到素数的概念，但是到目前为止我所尝试的都失败了。我最接近的尝试如下。

# counting confirmed primes. For loop should do remainder tests on
# all testNumbers, unless caught by the if statements that rule out
# multiples of 2,3,5,7 to speed things up. divisor increments by one
# on those numbers that do not get pulled by qualifying if statements

testNumber = 2
confirmedPrime = 0

while (confirmedPrime < 1001):
        for divisor in range(1, testNumber+1):
                if (testNumber/2)*2== testNumber:
                        testNumber += 1
                elif (testNumber/3)*3 == testNumber:
                        testNumber += 1
                elif (testNumber/5)*5 == testNumber:
                        testNumber += 1
                elif (testNumber/7)*7 == testNumber:
                        testNumber += 1
                elif(testNumber%divisor == 0):
                        testNumber += 1
        confirmedPrime +=1
print testNumber

然而，这并没有返回我期待的“7919”。它返回“7507”所以某处有一些复合材料从网上滑过。

我已经通过这个网站搜索并没有设法解决它，所以我想我会问。

4

2 回答 2

4

这里有一些问题，所以让我们一步一步来。

您首先设置初始值，这是完全合理的。

testNumber=2
confirmedPrime = 0

然后你进入一个while循环，继续直到变量的值confirmedPrime达到（即等于或大于）1001。我想你的任务是找到第1000个素数，但是这样做你实际上是在找到第 1001 个，因为while循环一直持续到confirmedPrime值为 1001。将其更改为

while(confirmedPrime < 1000):

您立即进入另一个循环，这是第一个问题，即使它不是给您错误答案的原因。

    for divisor in range(1, testNumber+1)
        if (testNumber/2)*2 == testNumber:
            ...

在循环内对2、3、5和 7 的乘数进行测试for没有任何意义，因为对于testNumber. 所以这部分测试应该移出 for 循环。

    if (testNumber/2)*2 = testNumber: # Why not use modulo here too for consistency?
        testNumber += 1
    elif ...
        ...
    else:
        for divisor in range(...):

下一部分是测试其他更大的除数。您正在测试 1 到 范围内的除数testNumber+1。我不确定您为什么要这样做，但这不是一个好主意，因为当您进行倒数第二次迭代时，您的模测试将始终返回零， testing testNumber%testNumber。所以你应该把它改成testNumber-1，实际上你可以在达到 的平方根时停止testNumber，但我会留给你去弄清楚为什么。

现在最大的问题来了：for循环结束后，你加confirmedPrimes1 而不实际检查你是否找到了一个素数。因此，只有当第一个测试都不是真的并且没有“除数测试”结果是真的时，confirmedPrimes才会发生递增。

使用下划线而不是混合大小写（这是不好的 python mojo）、一致的间距等重写：

import math

test_number = 7       # Already know up to 7
confirmed_primes = 4  # Already know about 2, 3, 5 and 7

while confirmed_primes < 1000:
    test_number += 1

    if test_number % 2 and test_number % 3 and test_number % 5 and test_number % 7:
        is_prime = True

        for divisor in range(11, int(math.sqrt(test_number))+1):
            if test_number % divisor == 0:
                is_prime = False

        if is_prime:
            confirmed_primes += 1

print test_number
于 2013-09-18T16:40:29.493 回答
2

我不完全了解您的算法应该如何找到素数。

如果一个数只能被 1 或他自己整除，则称它为素数。

另一个定义是，如果一个数不能被任何小于它的素数整除，则称它为素数。

这可以成为您算法的基础，大大加快了这个过程。

def nth_prime(n):
    prime_list = []
    current = 2
    count = 0
    while(count < n):
        is_prime = True
        for prime in prime_list:
            if current % prime == 0:
                is_prime = False
                break
        if is_prime:
            prime_list.append(current)
            count += 1
        current += 1
    return current - 1

print nth_prime(1000) # => 7919
于 2013-09-18T16:44:20.967 回答