Factor a number into primes

Let us examine how to factor a number into its prime components. Any number can be expressed as the product of several prime numbers.

• The number 8 is 2*2*2.
• The number 765 is 3*3*5*17.

This type of factorization is intriguing because it could potentially break current cryptographic algorithms. However, for very large numbers, finding the solution is so complex that it is practically impossible.

We can define the function as follows. It attempts to divide our number n by all possible numbers, starting with 2. If n is divisible by a divisor, we store it as a factor and continue with the next one.

def factorize(n):
    factors = []

    for divisor in range(2, int(n**0.5) + 1):
        while n % divisor == 0:
            factors.append(divisor)
            n //= divisor
    
    if n > 1:
        factors.append(n)
    return factors

Let us see an example by factoring 765.

number = 765
factors = factorize(number)
print(f"{number} = {'*'.join(map(str, factors))}")
# 765 = 3*3*5*17

Now, an example with a larger number. As you can see, the larger the number, the longer it takes to factor.

number = 10000004400000259
factors = factorize(number)
print(f"{number} = {'*'.join(map(str, factors))}")
# 10000004400000259 = 100000007*100000037

✏️ Exercises:

• Find a number that cannot be factored because it takes too long.
• Optimize factorize replacing the for loop with a while loop.