python - 计算千次素数

Question

这道题要求计算第 1000 个素数。我正在尝试解决这个问题，但我被卡住了。

有一些关于如何解决问题的指南。

为了帮助您入门，这里粗略列出了您可能应该遵循的阶段编写代码:

1. 初始化一些状态变量
2. 生成所有大于 1 的(奇数)整数作为素数候选
3. 对每个候选整数，检验它是否为素数
4. 一个简单的方法是测试是否有任何其他整数 > 1 均匀将候选人除以 0 余数。为此，您可以使用模块化算术，例如，表达式 a%b 返回之后的余数整数a除以整数b。
5. 您可能会考虑需要检查哪些整数作为除数 –当然，您不需要超出正在检查的候选人范围，但是您可以提前多久停止检查？
6. 如果候选人是质数，打印出一些信息让你知道你在哪里在计算中，更新状态变量
7. 当您达到某个适当的结束条件时停止。在制定这个条件，不要忘记你的程序没有生成第一个素数 (2)。使用这些想法来指导您的代码创建。

目前我的尝试是这样的

def calculate_thousandth_prime():
    j = 0
    for i in range(3,int(10e6)):
        if i%2 != 0:
            counter = 0
            for k in range(1, i):
                if i%k != 0:
                    counter += 1
            if counter == 0:
                print("This candidate is prime")
                j += 1
        if j == 1001:
            print("The number "+str(i)+" is the thousandth prime")
            break
    return 0

calculate_thousandth_prime()

我的代码卡在 i%k != 0 上。我一定是做错了什么……有什么帮助吗？

Answer 1

你有两个问题:

首先，您要搜索 for k in range(1, i):。因为每个数字，包括质数，都可以被 1 整除，所以你找不到任何质数。尝试搜索 range(2, i)。

其次，您正在检查 if i%k != 0:。您应该改为检查 i%k == 0。如果 i 可以被任意数 k 整除，则该数不是素数。

其实我发现了第三个问题:你有一个差一的错误。通过初始化 j=0，您的代码会将它找到的第一个素数视为“第零个”素数。代码将输出千零一素数，而不是千分之一素数。