This is a Python project implementing a function to calculate the factors of a given integer, ie. all of the numbers which divide into that number.

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

Source Code Links

If you prefer you can download the source code as a zip, 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|")

print("| codedrome.com |")

print("| Factorization |")

print("-----------------\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.7 main.py

The output is:

Program Output

-----------------

| codedrome.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