python - 在 Python 中查找下一个素数

Question

我有一个函数，它接受一个数字(例如 5)并返回输入数字后的第一个质数(在本例中为 7)。

这是我的代码:

def prime(n):
    np=[]
    isprime=[]
    for i in range (n+1,n+200):
        np.append(i)
    for x in range(2,199):
        for j in np:
            if x%j!=0:
                isprime.append(x)
    return min(isprime)

但是，此代码不起作用(它始终返回 2)。哪里错了？

Answer 1

你有一些错误，最明显的是 np 显然是潜在的素数(它从 n+1 开始，这是第一个符合你的条件的潜在数字“输入数字后的第一个素数”)，但你将 x 添加到你的主要列表中，它来自 range(2,199) ，你应该使用:

isprime.append(j)

结果你的素数测试也是错误的，你应该使用:

j % x != 0

最后，如果该条件在一种情况下为真，则不能附加数字，它在所有情况下都必须为真(其中 x 是满足 2 <= x < j 的整数)，因为这个你应该切换你的第二组 for 循环(x 循环应该是内部循环)，你也应该只循环到 j-1(被测试的数字)。此外，如果是 j % x == 0，您应该选择不添加项目:

for ...:
    val_is_prime = True
    for ...:
        if j % x == 0:
            val_is_prime = False
            break
    if val_is_prime:
        isprime.append(j)

这导致以下代码:

def prime(n):
    np=[]
    isprime=[]
    for i in range (n+1,n+200):
        np.append(i)
    for j in np:
        val_is_prime = True
        for x in range(2,j-1):
            if j % x == 0:
                val_is_prime = False
                break
        if val_is_prime:
            isprime.append(j)
    return min(isprime)

然后测试运行:

>>> prime(5)
7
>>> prime(13)
17
>>> prime(23)
29

---

请注意，还有其他一些可以提高效率的地方，但这个答案侧重于错误而不是改进