Python 素数查找器

Question

我制作了一个质数查找器，您可以在其中输入一个数字，它会告诉您它是否是质数。

while True:
    p = int(input('Enter a number '))
    for d in range(2, p):
        if p % d == 0:
            print(p, "is not a prime number!", d,"*", p//d,"=",p)
            break
        else:
            print(p, "is a prime number!")
            break

但是它显示的数字显然不是质数。我认为它只是将其除以 2，因为我尝试过的所有奇数都被输出为奇数。

谁能帮忙解决这个问题吗？

Answer 1

你必须检查所有的数字才能说它是素数。目前，您的循环在第一次检查时退出（即

d == 2

），如果

False

，则返回

p % 2 == 0

，否则

True

。

您应该将

else

语句放在循环末尾，如下所示：

while True:
    p = int(input('Enter a number '))
    for d in range(2, p):
        if p % d == 0:
            print(p, "is not a prime number!", d,"*", p//d,"=",p)
            break
    else:
        print(p, "is a prime number!")

仅当循环不以

else

结束时才执行

break

。这意味着如果没有找到任何除法器，则您的数字是质数。

此外，请注意，您不必在

p

之前检查数字，您可以在

sqrt(p)

处停止并两两迭代：

for d in range(3, int(p**0.5) + 1, 2)

。

Answer 2

fermets 公式是最简单的一种，但由于使用幂计算，可能会存在内存效率问题（除平方根法和 AKS 法外）

def prime(n):
    # you can replace the 2 with any coprime number
    if (n < 2): return False;
    if 2**(n-1)%(n) == 1: return True;
    return False

def range_primes(r):
    p = [2];
    for i in range(1, r):
        if prime(i) == True:
            p.append(i);
    return p;