Prime Factorization Calculator

This online factorization calculator finds all prime factors of the input number. The calculator demonstrates prime factors in the general form, as well as in the exponential form and the CSV format. Additionally, this factorization calculator can create a prime factor tree and find all (not just prime) factors of the given number.

Directions for use

To use this calculator to find prime factors of a number, enter the given number and press "Calculate." The calculator will return the number's prime factors in the general form, in the exponential form, and as a list in the CSV format.

You also have an option of creating a factorization tree and the possibility of finding all factors of the given number. Both of these options can be chosen by ticking a corresponding box.

Limitations on the input values

• Input values should be integers; decimals and fractions are not accepted.
• Only positive integers greater than 1 can be used as inputs.
• The length of the number cannot exceed 13 digits (without commas to separate the thousands), i.e., the value of the input number should be less than 10,000,000,000,000 or 10000000000000. The maximum input value is, therefore, 9,999,999,999,999 or 9999999999999.

Prime numbers and composite numbers

A prime number is a whole number greater than 1, that cannot be further divided into other whole numbers. In other words, a prime number is a whole number greater than 1 that cannot be made by multiplying other whole numbers. The smallest prime numbers are 2, 3, 5, 7, 11, 13, 17, … (Note how only one prime number is even – 2, all other prime numbers are odd).

The nth prime number in the above list can be denoted as Prime[n]. In that case, Prime[1] = 2, Prime[2] = 3, Prime[3] = 5, and so on. This online calculator will demonstrate the index n of each identified prime number up to n = 5000.

A composite number is a whole number greater than 1 that can be made by multiplying other whole numbers. For example, 6 is a composite number since 6 = 3 × 2. 12 is a composite number since 12 = 6 × 2 = 3 × 2 × 2.

Number factorization

The numbers you multiply to get another whole number are called factors. As demonstrated above, 3 and 2 are the factors of 6. Since 6 can also be found by multiplying 1 and 6: 6 = 1 × 6, 1 and 6 are also the factors of 6. Finally, all factors of 6 are 1, 2, 3, and 6.

The only factors of any prime number are 1 and the number itself. For example, factors of 17 are 1 and 17.

Prime factorization is the process of finding all prime numbers that can be multiplied to make the given number. Note that prime factorization of a number is different from finding all factors of that number.

For example, all factors of 12 are 1, 2, 3, 4, 6, 12. These factors are written as a list.

While prime factorization of 12 will look like this: 12 = 2 × 2 × 3. In prime factorization, we only get results in the form of prime numbers.

Prime Factorization Algorithm

Trial division

Let's look at the most intuitive prime factorization method, sometimes called the trial division method, on an example and identify the prime factors of 36. Since we know all prime numbers, we can check whether the given number is divisible by any of them. The easiest way is to start from the smallest prime number, which is 2:

36 ÷ 2 = 18

The result of this division is a whole number. Therefore, 2 is one of the prime factors of 36. But 18 is not prime yet, so we continue and check whether 18 is divisible by 2:

18 ÷ 2 = 9

9 is also a whole number. Therefore, 18 is divisible by 2.

Let's try again: 9 ÷ 2 = 4.5. This is not a whole number. Therefore, 9 is not divisible by 2.

Let's try the next prime number, 3. 9 ÷ 3 = 3. This is a whole number, so it worked! Moreover, 3 is already prime, which means we have reached the final step of the process! Now we just to need to write down the final answer:

36 = 2 × 2 × 3 × 3

This is the general way of writing down the prime factorization of a number. It can also be written using exponents like this:

36 = 2² × 3²

Prime Factors Tree

The prime factorization process can also be illustrated as a "tree." The prime factors tree for 36 will look like this:

Trial division (any factors)

Sometimes, the prime factorization process becomes easier if we first express the number as a multiplication of two other (not prime) numbers and then identify their prime factors. For example, let's find the prime factors of 48. It is easier to start with 48 = 6 × 8 since you probably know that by heart. Then we must find prime factors of 6: 6 = 2 × 3, and 8: 8 = 2 × 2 × 2. Finally, 48 = 2 × 2 × 2 × 2 × 3 = 2⁴ × 3¹.

Fundamental Theorem of Arithmetic

Any positive integer greater than 1 can be made from a unique set of prime factors. This theorem is sometimes called the Prime Factorization Theorem.

Real-life applications

Prime numbers are used in cryptography and cyber-security to encrypt and decrypt messages. We already know that any number can be represented as a product of a set of prime numbers and that this set is unique. This quality of prime numbers is what makes them so convenient for encryption.

Even more convenient is that finding prime factors of very large numbers remains a very time-consuming task, even for modern computers. That's also why the calculator on this page cannot work with infinitely large numbers.

The core principle behind using prime numbers for encryption is that it's relatively easy to take two large prime numbers and multiply them to create a much larger composite number. However, it is incredibly difficult to decompose that final number back into the original primes.

Imagine taking two 10-digit prime numbers and multiplying them to get a number with even more digits. Now imagine the process of prime factorization of that number by trial division…

This is such a long process that no computer can currently find two initial prime numbers in a given problem in any reasonable time. But this situation may change in the future with the development of quantum computers.