计算千次素数

Question

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

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

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

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

实际上，我发现了第三个问题：您有一个 off-by-one 错误。通过初始化 j=0，您的代码将其找到的第一个素数视为 "zeroth" 素数。该代码将输出 thousand-and-first 个素数，而不是第 000 个素数。

Answer 2

我所做的更改：

更改范围以添加 2 步骤以更自然地跳过偶数。
检查你的内循环，你需要除以值range(2, i//2)。除以任何大于 i//2 的值将小于 2。
更改您的素数检查以查看上述范围内的任何数字是否相除。如果是这样，我们就知道这个数字是假的。届时我们可以转到下一个数字。
我们想要 return 当素数计数器为 1000 时，您正在 return 第 1001 个素数。

def calculate_thousandth_prime():
    prime_counter = 0
    for i in range(3,int(10e6),2):
        prime = True
        for k in range(2, i//2):
            if i % k == 0:
                prime = False
                break
        if prime:
            print(str(i) + " is prime")
            prime_counter += 1
        if prime_counter == 1000:
            print("The number "+str(i)+" is the thousandth prime")
            break
    return i

calculate_thousandth_prime()

Answer 3

埃拉托色尼筛法通常是早期素数最快的方法。您可以调整它以达到第 n 个素数。

例如：

def nthPrime(N):
    sieve = [1]*(N**2)
    p     = 2
    for _ in range(N):
        while not sieve[p]: p += 1
        sieve[p::p] = [0]*len(sieve[p::p])
    return p

nthPrime(100) # 541

素数列表除数检查方法可能更容易编写和理解，但速度要慢得多（尽管只有 1000 个素数，这不会有太大区别）：

def nthPrime(N):
    primes = [2]
    p = 1
    while len(primes)<N:
        p += 2
        primes += [p]*all(p%d for d in primes)
    return p

计算千次素数

Calculating the thousandth prime

python

primes