Factorization

This is a simple Python project implementing a function to calculate the factors of a given integer, ie. all of the numbers which divide into that number. The core function returns a list of the factors of the number argument but as a bonus we can use that to write a generator function consisting of just one line of code!

To calculate the factors of a number n I will use a naive brute-force method called trial division which attempts to divide n by all numbers up to and including n - if there is no remainder the number is a factor. No number more than n/2 except n itself can be a factor of n so as an optimization I will only run the trial division on numbers up to n/2, and then add n to the factor list. Additionaly, 1 is a factor of all integers so it will be added to the list at the start and we will commence trial division at 2.

Create a new folder somewhere handy and create these two empty files in it:

  • factorization.py
  • main.py

If you prefer you can download the source code as a zip file from the Downloads page, or clone/download from Github. Open factorization.py and type or past the following code.

factorization.py

import math

def get_factor_list(n):

    """
    Use trial division to identify the factors of n.
    1 is always a factor of any integer so is added at the start.
    We only need to check up to n/2, and then add n after the loop.
    """

    factors = [1]

    for t in range(2, (math.ceil((n / 2) + 1))):
        if n % t == 0:
            factors.append(t)

    factors.append(n)

    return factors

#-------------------------------------------------------

def factors(n):

    """
    Generator function leveraging the get_factor_list function.
    """

    return iter(get_factor_list(n))

The get_factor_list function creates a list with a single value, 1, which is a factor of any integer so not worth checking. We then enter a loop to perform modular division of n by all numbers up to n/2 - if the result is 0 then the current number is a factor and can be added to the list. Finally we add n to the list and return it.

The function factors is a generator which is a special kind of function returning a type of iterator called a generator object. This function can then be called using for/in syntax to retrieve all values. In this particular case we already have the function get_factor_list to actually calculate factors so within the generator function we can call get_factor_list and pass the list it returns to the iter function. This creates an iterator which we can loop using for/in. All that with just a single line of code.

Now let's write a bit of code to test these functions.

main.py

import factorization

def main():

    """
    Test the get_factor_list function and factors generator on a few numbers.
    """

    print("----------------------\n| code-in-python.com |\n| Factorization      |\n----------------------\n")

    numbers_to_factorize = [15,19,25,50,77,99]

    #---------------------------------------

    print("factorization.get_factor_list\n-----------------------------")

    for n in numbers_to_factorize:

        factors = factorization.get_factor_list(n)

        print("Factors of {}: {}".format(n, factors))

    #---------------------------------------

    print("\nfactorization.factors (generator)\n---------------------------------")

    for n in numbers_to_factorize:

        print("Factors of {}: ".format(n), end="")

        for f in factorization.factors(n):
            print("{} ".format(f), end="")

        print("")

#-----------------------------------------------------

main()

At the top we import factorization and then within main create a list of numbers to factorize. We then iterate this list for the first time, calling get_factor_list on each item and printing the result.

We then iterate the numbers again, this time calling the generator using for/in. This time of course we get the factors one at a time instead of all together in a list.

That's the code finished so run it with this command:

Running the program

python3.6 main.py

The output is:

Program Output

----------------------
| code-in-python.com |
| Factorization      |
----------------------

factorization.get_factor_list
-----------------------------
Factors of 15: [1, 3, 5, 15]
Factors of 19: [1, 19]
Factors of 25: [1, 5, 25]
Factors of 50: [1, 2, 5, 10, 25, 50]
Factors of 77: [1, 7, 11, 77]
Factors of 99: [1, 3, 9, 11, 33, 99]

factorization.factors (generator)
---------------------------------
Factors of 15: 1 3 5 15
Factors of 19: 1 19
Factors of 25: 1 5 25
Factors of 50: 1 2 5 10 25 50
Factors of 77: 1 7 11 77
Factors of 99: 1 3 9 11 33 99

Please follow this blog on Twitter for news of future posts and other useful Python stuff.