Prime Factors Calculator

About this Calculator

This calculator will find all of the prime factors of a given number and present them as 1) a set of all prime factors, 2) as a set of each prime factor raised to the power of its frequency, and 3) showing the work for the current factorization through a Prime Factors Tree.

The n^th prime number can be denoted as Prime[n], so Prime[1] = 2, Prime[2] = 3, Prime[3] = 5, Prime[4] = 7, and so on.  See 1000 Prime Numbers.  When a prime number such as 1409 is entered and cannot be factored, the index Prime[223] = 1409 will be noted in the answer for n ≤ 1000.

What is Prime Factorization?

Prime factorization or integer factorization of a number is the determination of the set of prime numbers which multiply together to give the original integer.  It is also known as prime decomposition.

How do you find/do Prime Factorization of a Number?

The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 and 31, ...

Let's say we want to find the prime factors of 100.  We start testing all integers to see if and how often they divide 100 and the subsequent resulting quotients evenly. The resulting set of factors will be prime since, for example, when 2 is exhausted, all multiples of 2 will also be exhausted.

• 100 ÷ 2 = 50; save 2
• 50 ÷ 2 = 25; save 2
• 25 ÷ 2 = 12.5, not evenly so try next highest number, 3
• 25 ÷ 3 = 8.333, not evenly so try next highest number, 4
• 25 ÷ 4 = 6.25, not evenly so try next highest number, 5
• 25 ÷ 5 = 5; save 5
• 5 ÷ 5 = 1; save 5

The resulting factors are shown as a sequence of multiples 2 x 2 x 5 x 5 or consolidated as powers 2² x 5².

Examples

• Prime factorization of 100 is 2 x 2 x 5 x 5 or 2² x 5²
• Prime factorization of 76 is 2 x 2 x 19 or 2² x 19
• Prime factorization of 48 is 2 x 2 x 2 x 2 x 3 or 2⁴ x 3
• Prime factorization of 36 is 2 x 2 x 3 x 3 or 2² x 3²

Prime factorization tree

Using a prime factorization tree to show our work, prime decomposition of 100 looks like this:

	100
	/  \
2		50
		/  \
	2		25
			/  \
		5		5

References/ Further Reading

http://www.mathsisfun.com/prime-factorization.html

http://mathworld.wolfram.com/DirectSearchFactorization.html

http://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html

The Primes Page at http://primes.utm.edu/