计算第千个prim

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整除，则该数是而不是素数。你知道吗

事实上，我发现了第三个问题：你有一个off-by-one错误。通过初始化j=0，代码将找到的第一个素数视为“第零个”素数。代码将输出千和第一个素数，而不是千分之一个素数。你知道吗

Answer 2

我所做的更改：

1. 更改范围以添加2步骤以更自然地跳过偶数。你知道吗
2. 检查内部循环，需要除以值range(2, i//2)。除以任何大于i//2的值将小于2。你知道吗
3. 改变你的基本检查，看看是否有任何数字在上述范围内除以。如果是这样，我们就知道这个数字是假的。在那一点上我们可以进入下一个数字。你知道吗
4. 我们想在素数计数器为1000时返回，您返回的是第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