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

## What is factorization? And what is prime factorization?

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**, .

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.

## 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** $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!

## An example: the prime factorization of 20

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$.

## 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 $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$.

- If the result is
- 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!

- Yes! Perfect. Check the result. Is it
- 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.

## 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.