pyFindFactorsUsing3Methods

# Find divisors of a user-chosen integer
# THREE METHODS
# Mike Kerry - Jan 2022 - acclivity2@gmail.com

# Version 1 (Simplest)

# Start by getting an integer from the user.
# Note that as input() ALWAYS returns a string (like "1234") we need to convert it to an integer
# before we can do any arithmetic on it. The conversion is done by int() wrapped around input()
# BUT: if the user types anything non-numeric, our script will crash. We will fix that in version 2
number = int(input("Please choose a number to divide: "))

# Here we define an empty list.
# We need an empty list to start with, as we will be appending each divisor to it
divisorList = []

# This for loop will give us divisors from 1 up to and including the value of number (not beyond)
for div in range(1, number + 1):

    # number % div gives us the remainder when number is divided by div
    if number % div == 0:           # If the remainder is zero ...
        divisorList.append(div)     # then div is a true divisor of number. Append it to results list

# The loop from 1 to number has finished. Now we can print the results list
print(divisorList)

# ================ END OF VERSION 1 ================

# ========================================================
# Version 2. Better more "Pythonic" code

# In this version, we will verify that what the user types is numeric
# In our script version 1 above, the script would crash if the user either just hit enter,
# or typed any characters other then 0 through 9. This version avoids such a crash

# First we code a loop which will keep looping until we get a good integer from the user
while True:
    # get the user input as a string variable
    userin = input("Please choose a number to divide: ")

    # if the string variable contains only digits 0 to 9, then we break out of this loop
    if userin.isdigit():
        break

    # The user did not type a valid numeric input. Ask then to type again, and keep looping
    print("Invalid integer. Please enter again\n")

# Now we know that userin contains numeric data, so we can convert it safely to an integer (number)
number = int(userin)
# For this version, we don't need an empty results list, as we will print the divisors as we go

# Same loop as version 1. "div" will contain integers 1 to number in turn. Not beyond.
for div in range(1, number + 1):

    # "if not number % div": this computes the remainder and tests if there is no result (not ... i.e. 0)
    # This is "more Pythonic" than saying "if number % div == 0"
    if not number % div:
        # Now we can print this divisor, but follow it with a space, not end-of-line
        # This effectively is an incomplete print ... we are just building up a print line
        print(div, end=", ")

# Our divisor loop has finished.
# Now we can do the final stage of actually printing the line we were building
print()

# ========================== END OF VERSION 2 =====================


# ======================== VERSION 3 =========== MORE EFFICIENT =============
# Now we realise that we only need to divide 'number' by integers up to the square root of 'number'
# We will use the Python built-in function divmod() which gives us both the quotient and the remainder
# This will be MUCH faster for large numbers.
# e.g. for 12345678 we only need do 3513 divisions instead of over 12 million

# Code a loop that will keep repeating the whole script until the user types a non-numeric
while True:
    # Get the input from the user as a string. This will always be safe (won't crash)
    userin = input("Enter a number to find its divisors:\n(Any non-integer to quit) ")

    # In this version, if the user types anything non-numeric, we will simply terminate the script
    if not userin.isdigit():
        break                       # break out of the while loop, and end the script

    number = int(userin)            # convert user input from a string variable to an integer variable

    # For this efficient version, we will go back to using a list for our results
    # But we need two lists, one for divisors, one for quotients
    # The reason will become clear later (I hope!)
    divisorList = []
    quotientList = []

    # Now we compute the square-root of number. Note that we need an integer result, not a float
    limit = int(number ** 0.5)      # limit is the nearest integer below or equal to the square-root

    # Loop from 1 up to limit inclusive (not beyond)
    for div in range(1, limit + 1):

        # The very handy divmod() function gives us the quotient and remainder all in one go
        q, r = divmod(number, div)
        # q is the quotient of number divided by div
        # r is the remainder when number is divided by div

        if not r:                       # if the remainder is zero ...
            divisorList.append(div)     # append the divisor to our results list
            quotientList.append(q)      # append the quotient to the quotient list
            # The quotient is the second factor involved in this division
            # e.g. if number is 27 and div is 3, the quotient is 9 and both 3 and 9 are factors of 27
            # we don't need to divide by 9. We already know the factors 3 and 9

    # OK, we have computed all the divisors up to the square root. We now need to append all the
    # quotients to our results list, but putting them in the correct order (they are currently reversed)
    # we use the extend() method to concatenate the two lists
    divisorList.extend(quotientList[::-1])          # [::-1] reverses the quotient list
    print(divisorList)


# Result
# Enter a number to find its divisors: 12345678
# [1, 2, 3, 6, 9, 18, 47, 94, 141, 282, 423, 846,
# 14593, 29186, 43779, 87558, 131337, 262674, 685871, 1371742, 2057613, 4115226, 6172839, 12345678]