While loop example

Question

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')

This is an example for understanding while loop in a book I'm reading, I don't quite understand why a floor division and then y % x? Can someone please explain this piece of code, whats it doing?

Thanks!

Answer 1

The program prints at least one factor of an integer y, or if it has no factors (other than itself and 1), prints that y is prime.

It uses the variable x to try all possible factors greater than one. It starts at the floor of y divided by 2, because no number larger than half of y could be a factor. Using normal division rather than floor division could give you a fractional value if y is odd. (An even better solution is to start with the square root of y - if y is not prime, one of its factors will be less than or equal to its square root.)

Inside the loop, it tests y % x, which is the remainder after dividing y by x. If the remainder is zero, that means that x is a factor of y, and it prints it.

The else clause is executed at the end of the loop, unless a factor is found, in which case the "break" skips out of the loop and the else clause. So either a factor is found, or it's prime.

Here's the improved code with the indentation fixed:

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'