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.
Factorizing some numbers...


# 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

2 thoughts on “Factorization

    • 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s