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