python - 素性测试算法失败

Question

我创建了一个简单的素数测试算法，但是对于像 15 这样的数字它失败了。为什么？

number = int(input("Test if Prime: "))

print ("Is " + str(number) + " Prime?: ")

for i in range (2, number): 
  if number % i == 0: 
    print ("No")
    break
  else: 
    print ("Yes")

我尝试了一个带有其他变体的 elif 语句，但它仍然不起作用：

number = int(input("Test if Prime: "))

print ("Is " + str(number) + " Prime?: ")

for i in range (2, number): 
  if number % i == 0: 
    break
  elif number % i != 0: 
    print ("Yes")

任何帮助表示赞赏。

Answer 1

你在循环中有你的 else 条件。在任何时间点，它只会检查一个值......

修改你的 for 循环以打印出它正在检查的数字：

for i in range (2, number): 
  print (i)
  if number % i == 0: 
    print ("No")
    break
  else: 
    print ("Yes")

打印出来（数字 = 15）：

2
Yes
3
No

如果它打印出“否”数字，你就知道它有效 - 1次

要稍微修改您所做的，我们可以将其更改为：

flag = False
for i in range (2, number): 
  if number % i == 0: 
    print ("No")
    flag = True
    break
if (!flag)
  print("Yes")

所有这一切都是将 print 语句推到循环之外（对于一个素数，它必须不能被小于它的所有数字整除）。该标志确保您只打印出 True 或 False（您不想同时打印出两者）

Answer 2

这是我根据您的示例进行的快速重构：

def is_prime_simple(number):
    is_prime = True
    for i in range(2, number):
        if number % i == 0:
            is_prime = False
            break
    return is_prime

number = int(input("Test if Prime: "))

print ("Is " + str(number) + " Prime?: ")
print('Yes' if is_prime_simple(number) else 'No')

Answer 3

由于错误的缩进，否则将对所有非奇数除数执行

for i in range (2, number):
  if number % i == 0:
    print ("No")
      break
else: 
  print ("Yes")