Prime Factorization Calculator

Discover the fundamental theorem of arithmetics with our prime factorization calculator. This tool will explain thoroughly how to calculate the prime factors of any number. Here you will learn:

• What is the factorization of a number, and the prime factorization;
• What are prime numbers;
• Why does $1$ is not a prime number?
• How to calculate the prime factors of a number?
• A simple example: the prime factorization of 20;
• The prime tree number calculator: a visual representation of the prime number factorization.

We also have other handy tools that may be very convenient for solving some math problems you encounter. Give it a try and check our determinant solver or polynomial grapher!

In mathematics, the factors are the operators in a multiplication: in $2\times3$, $2$ and $3$ are the factors.

Writing a number as the result of the multiplication of a series of factors is called factorization. When decimal numbers are allowed, factorization is trivial, but when we restrict to integers and maintain that only multiplication is allowed, we are on an entirely different ground.

The integer factorization of a number is a bit of an "inverse" multiplication, where we find the factors from the product. Here's an example:

Looks easy? Think again! 😁 We can lay down some rules to find the factors, but the result may not be univocal:

And so on. This is where we can remove a bit of this uncertainty: let's restrict the possible factors to prime numbers and their powers only. If we do so, we obtain what we call prime factorization of a number. In the case of $264$, the prime factorization is:

Don't worry; we will spend some time on this!

What's a prime number? A primer

Prime numbers are the MVPs of maths. Endlessly mysterious, we all know them by their definition, numbers that are divisible only by $1$ and by themselves. We love them and think — we are pretty sure of this — that they are not like the other numbers. We sent them into space, trying to signal our supposed intelligence. We base our banking on them. We made gigantic leaps in understanding them, but there are gaping holes in our knowledge: take a look at the Wikipedia page for unsolved mathematical problems, prime numbers section.

Here are the first prime numbers:

And here's the last known by humanity (in May 2022: it will change soon):

A number with $24,862,048$ digits (we would need half of the Encyclopedia Britannica to write it down). We could use, e.g., the random number generator and check if the number is prime, but that is impossible for a simple computer, unfortunately.

The research of the prime factors of a number is a cornerstone of mathematics. Since Eucildes, the Greek mathematician, we know (with proof!) the fundamental theorem of arithmetics, which states that every positive integer greater than $1$ can be factorized in a set of prime numbers and their powers and that this factorization is unique.

This uniqueness of the prime factorization is the reason for which one is not a prime number, even though it technically satisfies all the conditions. If $1$ was prime, we would have an infinite number of "different" factorizations: $6=2\times3\times1$, but also $6=2\times3\times1\times1$, and so on. Keep that one out of your factors!

Take a simple number, $20$. We are going to calculate the prime factorization "freehand".

• First step: take that $2$ out!
  $20=2\times10$
• Hey, do it again!Until the number is even, we can factor out as many twos as possible.
  $20=2\times2\times5$
• That's it: $5$ is a prime number: $20-2^2\times5$.

There are several possible ways to calculate the prime factorization of a number. The most commonly used employs trial division to calculate the prime number tree.

This algorithm is by no means efficient, and in the worst case, it can be extremely lengthy and resource-hungry. There are better alternatives out there, but conceptually we will stick to this one: you will understand how to calculate the prime decomposition in a second without focusing on more abstract and complex math.

How to calculate factorization in prime numbers, then? First, choose the number, then:

• Start dividing it by $2$: if the number is even, you will find your first prime factor. Consider the result of the division as the new number. If the original number is not divisible by $2$, move on.
  • If the result is even, go back directly to the beginning: you can divide again by $2$.
• You finally ended up in an odd number: try the next prime number, $3$: is it a divisor?
  • Yes! Perfect. Check the result. Is it even? Go back to the beginning. Is it odd? Try again with $3$.
  • No. 😔 No worries, move on to the next step!
• Try the division by $5$. We skipped $4$, of course, since it would automatically be considered by two divisions by $2$. Repeat the same steps we followed for $3$.
• Go on! Repeat the steps till the result of the division is $1$.

This is when things get lengthy. Take the number $1,445,638$. It's even, good!

• $1,445,638/2=722,819$.
• Let's try $3$: nothing;
• Let's try $5$: nothing;
• Let's try $7$: nothing...

In a while, you would finally reach $722,819$. Yes: it's a prime number! Luckily, there's a workaround: you don't have to try numbers bigger than $\sqrt{n}$. Bigger than that, and you would have met the ""other" factor of the multiplication already: if $n=p\times q$, we reach a "midpoint" at $n=\sqrt{n}\times\sqrt{n}$$, with a "symmetric" progression.

Our prime factorization calculator will show you the prime number tree and calculate the prime decomposition (both in an expanded and short form).

The tree is not necessarily the one we found by dividing the number by increasingly big prime numbers, even though the result will be the same: look at the factors. Only the "intermediate factors" may change during the decomposition.

Calculating the prime factors of a number is a rather complex problem: in particular, the number of operations required to find the factors increases in a non-polynomial way. The time and resources needed to do so are then higher than, let's say, calculating the square root: the known algorithm are just not good enough.