Python Prime Factorization Calculator: An Efficient Algorithm

Prime factorization is the process of expressing a number as a product of its prime factors. A prime number is a number greater than 1 with exactly two distinct divisors: 1 and itself. For instance, the prime factorization of 56 is represented as 56 = 2 × 2 × 2 × 7, where both 2 and 7 are prime numbers.

Since 2 is the only even prime number, the first step in prime factorization is to count how many times 2 divides the number. Once all factors of 2 are removed, we only need to check for odd numbers up to the square root of the remaining value to find all prime factors.

In this post, I will provide you with Python code that you can use as a Prime Factorization Calculator. It requires an integer greater than 1, and if you input a prime number, it will simply return the number itself.

Python Code for Prime Factorization

import argparse
import math

def prime_factorization(n):
    """
    This function finds all prime factors of given number
    """
    factors = []

    #  Divide by 2 until n becomes odd; handling it separately to increase counter by 2 in the loop
    while n % 2 == 0:
        factors.append(2)
        n //= 2

    # Checking for odd factors from 3 to sqrt(n)
    for i in range(3, math.ceil(math.sqrt(n))+1, 2):
        while n % i == 0:
            factors.append(i)
            n //= i

    # If n is still greater than 2, it must be prime
    if n > 2:
        factors.append(n)

    return factors

def main():
    """
    This program finds prime factorization of a given number
    """
    # provide a number from command line
    parser = argparse.ArgumentParser(description="Prime factorization of a number")
    parser.add_argument("-num", type=int, required=True, help="provide a positive number")
    args = parser.parse_args()

    # check the number provide by user
    if args.num <= 1:
        print("provide an integer >1")
    else:
        print(f"Prime factorization of {args.num}: {'*'.join(str(v) for v in prime_factorization(args.num))}")

if __name__ == "__main__":
    main()

To run this code, save it as prime_factorization.py (or any preferred name you like) and execute it from the command line with a number greater than 1, as shown below:

python prime_factorization.py -num 100

Please let me know in the comments if you encounter any issues with the code.