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 where and (excluding the commutative property).

For example, and that is the only way to multiply prime numbers to get to .

```
# 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(_)
```

Advertisements

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

LikeLike

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.

LikeLiked by 1 person