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

This is a lame primality test.

% is the mod operator. It performs division and returns the remainder rather than the result of the division. For example, 5 // 2 == 2, and 5 % 2 == 1.

Commented:

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

Answer 2

the logic is:

if y modulo x is 0, it means that x is a dividor of y, so y has a factor. print that, and break out of the loop.

if not, decrease x by 1, and try again.

but some things are broken in this code:

1. the else statement position
2. the fact the 'print y is prime' is after the loop - it will always print it.

Answer 3

I think the program tries to find the biggest prime factors of y. If y is a prime factor it prints this as well.

Answer 4

x = y // 2 is for testing the numbers in the range x: 2..y/2.
A better approach would be to test only the numbers x: 2..sqrt(y)

Answer 5

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'

Answer 6

The code simply checks if the square root of x has been reached. Note that you can check the primality of a number by checking if the integers from 2 up to the square root of x divides x perfectly (without a remainder).

Answer 7

the % denotes a modulus which gives you the remainder of division...

and this code checks for prime Y and also checks if Y is a multiplier of x...

x = y // 2 #x=the division or modulus of y , 2

while x > 1: #you want to check if this is a division result or a modulus

if y % x == 0: # if y is a multiplier of x

  print(y, 'has factor', x) 

  break  # break the while loop

x -= 1 # decreament x

else: # this line executes if the wihle reached x > 1 and didnt break print(y, 'is prime')

so if y is a multiplier of x it will decreament x and the loop continue otherwise it will print y is prime

Answer 8

For any number (x) which is not prime, there would be a factor greater than 1 and less than (x/2). 9 = 3*3 The logic is to iterate through all the numbers <= x/2 and check if the number divides.