0
x = y // 2  # For some y > 1
while x > 1:
   if y % x == 0: # Remainder 
      print(y, 'has factor', x) 
      break  # Skip else
   x -= 1 
else: # Normal exit
   print(y, 'is prime')

这是在我正在阅读的书中理解 while 循环的示例,我不太明白为什么要进行地板除法,然后是 y % x?有人可以解释这段代码,它在做什么?

谢谢!

4

8 回答 8

4

这是一个蹩脚的素数测试

% 是mod 运算符。它执行除法并返回余数而不是除法的结果。例如,5 // 2 == 2 和 5 % 2 == 1。

评论:

x = y // 2  # For some y > 1  ##Reduce search space to half of y
while x > 1:
  if y % x == 0: # Remainder  ##If x divides y cleanly (4 / 2 == 2)
    print(y, 'has factor', x) ##y is not prime
    break  # Skip else        ##Exit the loop
  x -= 1   # Normal exit  ##Try the next value
else:
  print(y, 'is prime')
于 2009-12-09T07:54:59.460 回答
1

逻辑是:

如果 y 模 x 为 0,则表示 x 是 y 的除数,因此 y 有一个因数。打印出来,然后跳出循环。

如果不是,请将 x 减 1,然后重试。

但是这段代码中有一些东西被破坏了:

  1. else 语句位置
  2. “打印 y 是素数”的事实是在循环之后 - 它总是会打印它。
于 2009-12-09T07:55:07.213 回答
1

该程序打印整数 y 的至少一个因子,或者如果它没有因子(除了它自己和 1),则打印 y 是素数。

它使用变量 x 来尝试所有大于一的可能因子。它从 y 除以 2 开始,因为没有大于 y 一半的数字可能是一个因素。如果 y 是奇数,则使用正常除法而不是下除法可以给您一个小数值。(一个更好的解决方案是从 y 的平方根开始 - 如果 y 不是素数,它的一个因数将小于或等于它的平方根。)

在循环内部,它测试 y % x,即 y 除以 x 后的余数。如果余数为零,则表示 x 是 y 的因数,它会打印出来。

else 子句在循环结束时执行,除非找到一个因子,在这种情况下,“break”会跳出循环和 else 子句。所以要么找到一个因子,要么它是素数。

这是固定缩进的改进代码:

import math

def check_primality(y):
  x = int(math.sqrt(y))
  while x > 1:
    if y % x == 0:                                                
      print y, 'has factor', x
      break
    x -= 1
  else:
    print y, 'is prime'
于 2009-12-09T07:59:36.447 回答
1

该代码仅检查是否已达到 x 的平方根。请注意,您可以通过检查从 2 到 x 的平方根的整数是否完美地整除 x(没有余数)来检查数字的素数。

于 2009-12-09T07:59:44.153 回答
1

对于任何不是素数的数 (x),都会有一个大于 1 且小于 (x/2) 的因数。9 = 3*3 逻辑是遍历所有 <= x/2 的数字并检查数字是否相除。

于 2009-12-09T08:09:43.813 回答
0

我认为该程序试图找到 y 的最大素因数。如果 y 是主要因素,它也会打印出来。

于 2009-12-09T07:55:19.850 回答
0

x = y // 2用于测试 x: 范围内的数字2..y/2
更好的方法是只测试数字 x:2..sqrt(y)

于 2009-12-09T07:57:32.873 回答
0

% 表示一个模数,它给你除法的余数......

此代码检查素数 Y 并检查 Y 是否是 x 的乘数...

x = y // 2 #x=y​​ 的除法或模数, 2

while x > 1: #你想检查这是除法结果还是模数

if y % x == 0: # 如果 y 是 x 的乘数

  print(y, 'has factor', x) 

  break  # break the while loop

x -= 1 # decreament x 

else: # 如果 wihle 达到 x > 1 并且没有中断 print(y, 'is prime'),则执行此行

所以如果 y 是 x 的乘数,它将递减 x 并且循环继续,否则它将打印 y is prime

于 2009-12-09T08:04:36.670 回答