质数计算器没有输出 (python)

Question

我正在尝试使用基本逻辑找到第 10001 个素数： 1）判断一个数是否为质数 2）如果素数则将其添加到列表中 3) 打印列表中的第 10001 项

这是我的代码：

primelist=[]
import math
i=2
while True:
    for x in range(2, int(math.sqrt(i))):
        if i % x == 0:
            continue
        else:
            primelist.append(i)
    if len(primelist)== 10001:
        break 
print(primelist[-1])

逻辑或代码是否根本错误或效率低下？

我可以做些什么来改善/让它发挥作用？

编辑 我增加了 i (i+=1) 并使用 all() 检查是否所有内容都是不可分割的，以回应评论

primelist=[2]
import math
i=3
while True:
    for x in range(2, int(i**(1/2))):
        if all(i%x!=0 for x in range(2, int(math.sqrt(i)))):
            primelist.append(i)
    i+=1
    if len(primelist)== 10001:
        break
print(primelist[-1])

Answer 1

如果你想继续使用你的算法，这个应该有用：

import math

def is_prime(n):
    for x in range(2, int(math.sqrt(n)) + 1):
        if n % x == 0:
            return False
    return True

primelist = []
i = 2

while True:
    if is_prime(i) is True:
        primelist.append(i)
    i += 1
    if len(primelist) == 10001:
        break
print(primelist[-1])

Answer 2

保持 algorithm/code 结构不变（未做优化），这样我们就可以轻松共享几个语言点，请参阅内联评论：

primelist=[]
import math
i=2
while True:
    #changed to sqrt + 1, the second parameter of range is not inclusive, 
    #by adding 1, we make sure sqrt itself is included
    for x in range(2, int(math.sqrt(i) + 1)):
        if i % x == 0:
            #you want break not continue, continue will try 
            #next possible factor, since you already figured out that this 
            #is not a prime, no need to keep trying 
            #continue
            break
    #a for/else block, many python users never encountered this python
    #syntax. The else block is only triggered, if the for loop is naturally
    #completed without running into the break statement
    else:
        #a little debugging, to visually confirm we generated all primes
        print("adding {}".format(i))
        primelist.append(i)
    if len(primelist)== 11:
        break 
    #advance to the next number, this is important, 
    #otherwise i will always be 2
    i += 1
print(primelist[-1])

如需优化算法，在线搜索"prime sieve"。

Answer 3

这是您的代码的一个版本，速度稍快，并且不使用太多 RAM。我们真的不需要建立我们找到的素数的列表。我们不使用该列表中的数字来查找更多素数，我们实际上只对它的长度感兴趣。因此，我们没有构建列表，而是只记录我们找到的素数。

# Include 2 in the count
count = 1
i = 3
while True:
    if all(i % x for x in range(3, int(i ** 0.5) + 1, 2)):
        count += 1
    if count == 10001:
        break
    i += 2

print(i)

FWIW，这是一个使用筛分的更快解决方案。我们使用素数定理估计所需的筛子尺寸。 Wikipedia 给出 p(n) 的边界，第 n 个素数，对 n >= 6 有效：

log(n) + log(log(n)) - 1 < p(n) / n < log(n) + log(log(n))

我们使用上限作为筛选中的最高数。对于 n < 6，我们使用硬编码列表。

为了节省space，这个筛子只能容纳奇数，所以我们把p(1) == 2的情况作为一个特例。

#!/usr/bin/env python3

''' Use a sieve of Eratosthenes to find nth prime

    Written by PM 2Ring 2017.05.01
    Sieve code derived from primes1 by Robert William Hanks
    See 
'''

from math import log
from sys import argv

def main():
    num = int(argv[1]) if len(argv) > 1 else 10001

    if num == 1:
        # Handle 2 as a special case
        print(1, 2)
        return
    elif num < 6:
        # Use a pre-built table for (3, 5, 7, 11)
        primes = [1, 1, 1, 1, 0, 1]
    else:
        # Compute upper bound from Prime number theorem
        x = log(num)
        hi = int(num * (x + log(x)))
        print('upper bound', hi)

        # Create a boolean list of odd primes in range(hi)
        primes = [True] * (hi//2)
        for i in range(3, 1 + int(hi**0.5), 2):
            if primes[i//2]:
                primes[i*i//2::i] = [False] * ((hi - i*i - 1) // (2*i) + 1)

    # Count the primes until we get the nth one
    k = 0
    for i, b in enumerate(primes):
        if b:
            k += 1
            if k == num:
                break

    print(num, 2*i+1)


if __name__ == "__main__":
    main()

此代码在我的旧单核 32 位 2GHz 机器运行 Python 3.6.0 上用不到 0.15 秒的时间找到 p(10001) = 104743。它在大约 2.2 秒内找到 p(500000) = 7368787。

质数计算器没有输出 (python)

Prime number calculator produces no output (python)

python

primes

python-3.x