Prime factorisation calculator with steps and a factor tree

Type a number, and the solver breaks it into prime factors step by step, builds a factor tree, finds all the divisors and checks the answer.

Examples: 360 1001 97 divisors of 360 2^32 + 1 600,851,475,143 10!

Loading the solver…

What you can type

Any positive integer up to sixty digits: 360, 600,851,475,143 (commas or spaces between the thousands are fine). Or an expression whose value you want factorised: 2^32 + 1, 10!, 2·3·5·7 + 1. With the word “divisors” (divisors of 360) the solver lists all the divisors of the number and their sum, and to the question is 97 prime it answers “yes” or “no” and explains why.

How to factorise: dividing in order

A prime is a positive integer greater than one that is divisible only by $1$ and itself: $2, 3, 5, 7, 11, 13, \ldots$ The other numbers greater than one are composite: they can be written as a product of smaller ones. We’ll factorise a number the way it’s done on paper, by repeated division in a column.

Try dividing by the primes in increasing order: $2, 3, 5, 7, 11, \ldots$
While the number is divisible by the current prime, divide and write that prime in the right-hand column.
When it stops dividing, move on to the next prime.
Stop when what’s left is one. Or sooner: when the square of the next prime is already bigger than what’s left, the remainder is itself prime.

The divisors found this way are always prime: the number has already been divided “to the end” by all the smaller primes, so a composite divisor never gets a chance to appear. There’s no point checking whether the number is divisible by $4$, $6$ or $9$. Divisibility tests speed things up: by $2$, the last digit is even; by $3$, the digit sum is divisible by $3$; by $5$, the number ends in $0$ or $5$; by $11$, the difference between the sums of alternate digits is divisible by $11$.

Why is it enough to go up to the square root? If $n = a \cdot b$ and both factors are bigger than $\sqrt{n}$, their product is bigger than $n$. So a composite number always has a prime divisor no bigger than $\sqrt{n}$. If there isn’t one, the number is prime.

Why the factorisation is unique

However you factorise a number, starting with two, with five, or first splitting it into two “convenient” factors as in the tree in the solver’s picture, you end up with the same prime factors. That’s not an observation but a theorem.

Distinct primes, usually written in increasing order: $p_1 < p_2 < \ldots < p_k$.

Positive exponents: how many times each prime occurs in the factorisation.

Every positive integer $n > 1$ can be written this way, and in only one way (up to the order of the factors). Example: $360 = 2^3 \cdot 3^2 \cdot 5$. You can split $360$ as $18 \cdot 20$, as $4 \cdot 90$ or as $2 \cdot 180$, but the prime factors will always be three twos, two threes and one five.

Existence is easy to prove: keep splitting while you can, and the numbers keep getting smaller. Uniqueness is harder and rests on a property of primes: if a prime $p$ divides a product $ab$, it divides $a$ or $b$. This also answers the question of why one isn’t counted as a prime: otherwise factorisations would stop being unique ($6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3\ldots$). The proof and the history are in the chapter on primes.

How many divisors a number has

The factorisation shows all the divisors at once. Every divisor of $360 = 2^3 \cdot 3^2 \cdot 5$ is made of the same primes to powers no higher: two to a power from $0$ to $3$, three from $0$ to $2$, five from $0$ to $1$. The powers are chosen independently of one another.

The exponents from the factorisation $n = p_1^{a_1} \cdots p_k^{a_k}$. One is added because a power can also be zero: the prime can be left out altogether.

Example: $\tau(360) = (3 + 1)(2 + 1)(1 + 1) = 24$. The sum of the divisors is computed in a similar way: $(1 + 2 + 4 + 8)(1 + 3 + 9)(1 + 5) = 15 \cdot 13 \cdot 6 = 1170$; expand the brackets and each divisor appears exactly once.

A prime has exactly two divisors, the square of a prime has three ($1$, $p$, $p^2$). Only perfect squares have an odd number of divisors: the divisors pair up as $d$ and $n/d$, and only $\sqrt{n}$ is left without a partner.

Worked examples

Example 1. 360

Divide by $2$ while you can: $360 \to 180 \to 90 \to 45$, three times. $45$ is odd, so move on to $3$: the digit sum $4 + 5 = 9$ is divisible by $3$, and $45 \to 15 \to 5$, twice. Five isn’t divisible by $3$, but it is by $5$: $5 \to 1$.

$$\begin{array}{r|l} 360 & 2 \\ 180 & 2 \\ 90 & 2 \\ 45 & 3 \\ 15 & 3 \\ 5 & 5 \\ 1 & \end{array} \qquad 360 = 2^3 \cdot 3^2 \cdot 5.$$

Example 2. 1001

It isn’t divisible by $2$ (it’s odd), nor by $3$ (the digit sum is $2$), nor by $5$. It is divisible by $7$: $1001 = 7 \cdot 143$. The number $143$ isn’t divisible by $7$ ($7 \cdot 20 = 140$, remainder $3$), but it is by $11$: $143 = 11 \cdot 13$. And $13$ is prime.

$$1001 = 7 \cdot 11 \cdot 13.$$

That’s why the trick “write a three-digit number twice in a row and you get a multiple of $7$, $11$ and $13$” always works: $\overline{abcabc} = \overline{abc} \cdot 1001$.

Example 3. Is 97 prime?

$\sqrt{97} \approx 9.8$, so it’s enough to check the primes $2, 3, 5, 7$. $97$ is odd; the digit sum $16$ isn’t divisible by $3$; it doesn’t end in $0$ or $5$; $97 = 7 \cdot 13 + 6$. None of them works, so $97$ is prime. There’s no need to check $11$ and beyond: $11^2 = 121 > 97$.

Example 4. $2^{32} + 1$

Pierre de Fermat noticed that the numbers $2^{1} + 1 = 3$, $2^{2} + 1 = 5$, $2^{4} + 1 = 17$, $2^{8} + 1 = 257$ and $2^{16} + 1 = 65{,}537$ are prime, and conjectured that this always happens. In 1732 Euler factorised the next one: $2^{32} + 1 = 4{,}294{,}967{,}297 = 641 \cdot 6{,}700{,}417$. The solver finds this factor by trial division: $641$ is the 116th prime.

What if the number is big?

Trial division is good for numbers whose factors are all small. If a large chunk is left after dividing by the primes up to ten thousand, the solver first checks whether it’s prime (the Miller–Rabin test), and if it isn’t, looks for a divisor with Pollard’s rho method, which finds a factor $p$ in about $\sqrt{p}$ steps instead of $p$. That’s how numbers like $600{,}851{,}475{,}143 = 71 \cdot 839 \cdot 1471 \cdot 6857$, and even products of two thirteen-digit primes, are factorised in a fraction of a second.

But a number made of two prime factors of a hundred digits each can’t be factorised in reasonable time by this solver or by the most powerful computer. That’s what the RSA cipher that protects banking connections rests on: multiplying two primes is easy, but factorising the product back is practically impossible. The record for publicly factorising such a number is RSA-250, $829$ bits, factorised in 2020; the computation took about 2700 years of work for a single processor core. How the cipher works is explained in the chapter on modular arithmetic.

Common mistakes

Leaving a composite factor. $360 = 4 \cdot 9 \cdot 10$ is a factorisation, but not into primes: $4$, $9$ and $10$ must be broken down further.
Losing repeated factors. $360 = 2 \cdot 3 \cdot 5$ is wrong: that’s $30$. Two occurs three times and three occurs twice; keep dividing while you can.
Writing one as a factor. $1$ isn’t a prime and isn’t included in the factorisation.
Taking a composite number for a prime. The classic traps: $51 = 3 \cdot 17$, $57 = 3 \cdot 19$, $91 = 7 \cdot 13$, $221 = 13 \cdot 17$. They look “prime”, but each has a divisor below its square root.
Stopping before the square root. To prove that $221$ is prime, checking $2, 3, 5, 7, 11$ isn’t enough: $\sqrt{221} \approx 14.9$, and it is divisible by $13$.
Counting divisors from the exponents without adding one. $2^3 \cdot 3^2$ has not $3 \cdot 2 = 6$ divisors but $(3 + 1)(2 + 1) = 12$.