Creating a next_factor function in Python

next_factor.py

### Part 0: We would like to have this function to use, but it's probably in your code already.

def is_factor(f, n):
  return (n % f == 0)

### Part 1: First we write a testing function.

def test_next_factor():
  nf = next_factor
  assert nf(10,3)  == 5
  assert nf(10,4)  == 5
  assert nf(10,5)  == 5     # Should this be 5 or 10? That's a decision to make.
  assert nf(10,6)  == 10
  assert nf(10,7)  == 10
  assert nf(10,10) == 10
  assert nf(10,11) == None

### Part 2: A function definition with a comment.

# next_factor(n,f) returns the first factor of n that is >= f, or None if f > n.
def next_factor(n, f):
  pass

### Part 3: An implementation.

# next_factor(n,f) returns the first factor of n that is >= f, or None if f > n.
def next_factor(n, f):
  for i in range(f, n+1):
    if is_factor(f, n):
      return f
  # If we get this far...
  return None

# Does the above function pass the tests?

### Part 4: Improve efficiency.

# If we called next_factor(99, 65), we know mathematically that the answer is 99, so we should
# return that straight away.
#
# And while we are considering special cases, we could treat f > n as special.

# next_factor(n,f) returns the first factor of n that is >= f, or None if f > n.
def next_factor(n, f):
  if f > n:
    return None
  if f > n // 2:
    return n
  for i in range(f, n+1):
    if is_factor(f, n):
      return f
  # If we get this far... (We shouldn't, because of the opening if statement.)
  return None

# Does this pass the tests?

### Part 5: One more look.

# Look at the range(f, n+1) in the function. I think this will lead to some inefficient code.
# Consider n = 1005, which is divisible by 3 but not by 2, so the highest possible factor for
# this number is 335. If we call next_factor(1005, 338), it will pass the first two if statements
# and then try 338, 339, 340, ..., 1005. We would like to stop it short.

# next_factor(n,f) returns the first factor of n that is >= f, or None if f > n.
def next_factor(n, f):
  if f > n:
    return None
  for i in range(f, n//2):
    if is_factor(f, n):
      return f
  # If we get this far...
  return None

# This should now be ready to use in the pf function.