# Factorization

Playing around with prime numbers, I created this simple factorization program.
The interesting thing about prime factors is that they are unique. There can only be one way to multiply prime numbers to get $n$ where $n \in \mathbb{N}$ and $n \geq 2$ (excluding the commutative property).
For example, $2 \cdot 3 \cdot 7 = 42$ and that is the only way to multiply prime numbers to get to $42$.

# Python 2.7.7 Code
# Jonathan Frech 8th of April, 2016

# factorize n
def factor(n):
factors = []
while n > 1:
for _ in range(2, n+1):
if n % _ == 0:
factors.append(_)
n /= _
break

return factors

# execute the factorisation
def exe(n):
print ">>> factor(" + str(n) + ")"
print factor(n)
print

# examples
for _ in [10, 100, 1000, 10000, 88, 2345, 131313, 30135]:
exe(_)

## 2 thoughts on “Factorization”

1. Nice. You can actually check until n/2, that would be enough.

Like

• When checking if n is prime or not you can test divisors up to n, n/2 or even sqrt(n).
In this case however, I am not trying to check if n is prime but rather check all divisors of n.
For example: when checking if 11 is prime or not, I can test if the numbers {2, 3, 4} divide 11 and conclude that 11 is prime. If I instead want to calculate the divisors of 11, I need to check for {2, 3, 4, 5, 6, 7, 8, 9, 10, 11} and conclude that 11 has only one prime factor, 11.

Liked by 1 person

This site uses Akismet to reduce spam. Learn how your comment data is processed.