时间戳

首页 > 解决方案 > 素性测试算法失败

python - 素性测试算法失败

问题描述

我创建了一个简单的素数测试算法，但是对于像 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")

任何帮助表示赞赏。

标签： pythonalgorithmnumbersprimesprimality-test

解决方案

你在循环中有你的 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（您不想同时打印出两者）

推荐阅读