在Python中，编写一个脚本来确定用户输入的数字是否是质数。

Question

编写脚本以确定用户输入的数字是否为质数，并根据您的脚本找到的结果打印“您输入的数字是质数”或“您输入的数字不是质数”。

我的代码无法通过某些测试用例，我不确定为什么。我在这里看到一些答案涉及计算平方根，但我不明白为什么会有帮助。

num= int(input())

if num == 0 or num ==1:
    print('The number you inputted is not a prime number.')
while num < 0:
    break
if num > 0:
    for i in range(2,num):
        if num%i==0:
            print('The number you inputted is not a prime number.')
            break
        else:
            print('The number you inputted is a prime number.')
            break

无论我使用几个测试用例，代码始终是正确的，但它无法通过我的作业任务。

- EmKhay

---

我在这里看到一些答案涉及计算平方根，但我不明白为什么这会有益。- https://proofwiki.org/wiki/Composite_Number_has_Prime_Factor_not_Greater_Than_its_Square_Root - Mitch Wheat

平方根的原因是为了提高效率。以数字16为例，它有以下因数：(1, 16), (2, 8), (4, 4), (8,2), (16,1)。由于16的平方根是4，测试超过4的任何数字都是多余的。 - sin tribu

此外，您不需要测试任何非质数的数字。由于4是2和2的因子，因此测试2、4甚至8都是多余的。对于这个问题可能帮助不大，但您至少可以忽略2以外的偶数。 - sin tribu

仅检查奇数并且到候选数的平方根是一个不错的开始。你可以考虑的最后一个优化是，奇素数> 3总是以(6k ± 1)的形式出现，其中k为整数，因为6k、6k ± 2和6k ± 4都是偶数，6k ± 3可被3整除，而6k + 5 ≡ 6k - 1。 - gmds

注意：如果没有小的质因数，试除法会很慢。Baillie-PSW目前是最好的方法（对于小的数字有保证的结果，即使对于大的数字也没有已知的反例）。 - o11c

Answer 1

你的逻辑是错误的；只有在条件评估为True时，你才应该中断，因为你需要测试所有小于num ** 0.5（即你代码中的num）的数字。9就是一个非素数的例子，但你的代码将其评估为素数。

你需要像这样的代码：

prime = True
if num > 0:
    for i in range(2,num):
        if num % i == 0:
            prime = False
            break

    if prime:
        print(f'{num} is a prime number.')

    else:
        print(f'{num} is not a prime number.')

在开始时将 prime 设置为 True，仅当发现因子时将其更改为 False，我们可以在对所有值的条件进行评估后告诉是否该数是素数。

- gmds

---

啊！被忍者抢先了。:P - daviewales

Answer 2

问题出现在以下逻辑中：

for i in range(2,num):
    if num%i==0:
        print('The number you inputted is not a prime number.')
        break
    else:
        print('The number you inputted is a prime number.')
        break

为了找到问题所在，请尝试使用您的代码检查9是否为质数。 您的for循环执行以下操作:

1. i = 2
2. if num % i == 0，不是质数，跳出。
3. else，是质数，跳出。

这意味着您的for循环保证在i==2时停止。 换句话说，根据此算法，您对质数的定义是“任何奇数”。

要解决此问题，您需要找到一种方法，允许循环在所有剩余可能的除数之间迭代，而不是在第一次迭代后中断。

我会在此处停止，让您有机会自己找出其余部分。如果您无法取得任何进展，请告诉我，我将给出另一个提示。

- daviewales