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 11 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!

What is factorization? And what is prime factorization?

In mathematics, the factors are the operators in a multiplication: in 2×32\times3, 22 and 33 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:

264=4611264=4\cdot6\cdot11

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

264=2132264=388264=2411\begin{align*} 264&=2\cdot132\\ 264&=3\cdot88\\ 264&=24\cdot11 \end{align*}

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 264264, the prime factorization is:

264=23311264=2^3\cdot3\cdot11

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 11 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:

2,3,5,7,11,13,177,19,23,29...2,3,5,7,11,13,177,19,23,29...

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

282,589,93312^{82,589,933} − 1

A number with 24,862,04824,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.

What is prime factorization — in detail

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 11 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 11 was prime, we would have an infinite number of "different" factorizations: 6=2×3×16=2\times3\times1, but also 6=2×3×1×16=2\times3\times1\times1, and so on. Keep that one out of your factors!

An example: the prime factorization of 20

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

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

How to calculate the prime factors of a number?

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 22: 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 22, move on.
    • If the result is even, go back directly to the beginning: you can divide again by 22.
  • You finally ended up in an odd number: try the next prime number, 33: is it a divisor?
    • Yes! Perfect. Check the result. Is it even? Go back to the beginning. Is it odd? Try again with 33.
    • No. 😔 No worries, move on to the next step!
  • Try the division by 55. We skipped 44, of course, since it would automatically be considered by two divisions by 22. Repeat the same steps we followed for 33.
  • Go on! Repeat the steps till the result of the division is 11.

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

  • 1,445,638/2=722,8191,445,638/2=722,819.
  • Let's try 33: nothing;
  • Let's try 55: nothing;
  • Let's try 77: nothing...

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

How to use our prime factorization calculator: the prime number tree visualization.

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.

The problem of prime factorization

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.

Davide Borchia
Number
Extra options
Show
factorization tree (full)
People also viewed…

Cone volume

Our cone volume calculator will help you with your homework, telling you the volume of both cones and truncated cones in just a second!

Matrix determinant

Use this matrix determinant calculator to find the determinant of up to 4x4 size matrices.

Schwarzschild radius

Discover the fundamental of black hole physics with our Schwarzschild radius calculator.
main background