Prime Factorization

Prime factorization breaks a positive integer down into its prime number components: the unique set of prime numbers that multiply together to produce the original number. This tool is used by students learning number theory, anyone simplifying fractions, and developers working with divisibility and cryptography.

How to Use the Prime Factorization Tool

1. Enter a positive integer greater than 1 into the input field.
2. Click Factorise to calculate the prime factorisation.
3. Review the result expressed as a product of primes, with exponents where applicable.
4. Use the factor tree diagram to visualise how the number was broken down step by step.
5. Apply the result to simplify fractions, find GCF or LCM, or solve number theory problems.

The Formula

Every integer greater than 1 is either prime itself or can be written as a unique product of primes (the Fundamental Theorem of Arithmetic):

n = p1^a1 x p2^a2 x p3^a3 x ...

Where p1, p2, p3... are prime numbers and a1, a2, a3... are their respective exponents.

Method: divide n by the smallest prime that divides it evenly. Repeat with the quotient until the quotient is 1. Collect all divisors used.

Real-World Example

Find the prime factorisation of 360.

360 / 2 = 180 180 / 2 = 90 90 / 2 = 45 45 / 3 = 15 15 / 3 = 5 5 / 5 = 1

Prime factors used: 2, 2, 2, 3, 3, 5

Result: 360 = 2^3 x 3^2 x 5

Verify: 8 x 9 x 5 = 8 x 45 = 360. Correct.

This factorisation is unique: no other combination of primes multiplies to 360.

Why Prime Factorisation Matters

Prime factorisation is a fundamental operation in mathematics with widespread practical applications. It is the most reliable method for finding the GCF and LCM of two numbers: the GCF takes the lowest power of each shared prime factor, while the LCM takes the highest power of every prime factor present in either number. Simplifying fractions depends on cancelling shared prime factors in numerator and denominator. In cryptography, the RSA algorithm generates public and private keys based on the difficulty of factorising very large numbers (typically hundreds of digits) that are products of two enormous primes. The contrast between the ease of multiplying primes and the difficulty of factorising their product is what makes RSA secure. Prime factorisation also appears in solving Diophantine equations, computing modular inverses, and understanding the structure of algebraic rings.

Frequently Asked Questions

Is the prime factorisation of a number unique? Yes. The Fundamental Theorem of Arithmetic guarantees that every integer greater than 1 has exactly one prime factorisation (ignoring the order of factors). This uniqueness is what makes prime factorisation so powerful as a mathematical tool and why it is the foundation of so many algorithms.

What is a factor tree? A factor tree is a visual diagram showing how a number is progressively divided into smaller factors until all branches end at prime numbers. For example, 360 splits into 2 and 180, then 180 splits into 2 and 90, and so on. Factor trees are a popular teaching method in primary and secondary schools because they make the process intuitive.

Can very large numbers be factorised quickly? For numbers with only a few digits, factorisation is instant. For numbers with dozens of digits, modern computers can factorise them in seconds to minutes. However, for numbers with hundreds of digits that are products of two large primes, no known efficient algorithm exists. This computational difficulty is precisely what cryptographic systems like RSA rely on for security.

What is the prime factorisation of a prime number? A prime number is its own prime factorisation. For example, the prime factorisation of 13 is simply 13^1. It has no smaller prime factors, which is the definition of being prime.

Why does the tool start again from 2 on the new quotient?

Restarting from the smallest prime keeps the method easy to follow and costs almost nothing on numbers of a few digits. A quotient cannot have a prime factor smaller than the last prime that divided the original number, so a faster version carries the last divisor forward. Both approaches return the same factorisation. Plug your own number into the tool above.

How do I check that a factorisation is complete?

Multiply the factors and compare the product with the number you entered. Then confirm each factor is prime by testing primes up to its square root. Those two checks cover the whole answer and take seconds by hand up to four digits.

What is the largest number worth factorising by hand?

Four or five digits, and only when the factors are small. The work grows with the number of primes below the square root, so a six-digit number can need a hundred tests and a nine-digit number can need thousands. The tool above handles the arithmetic for any size the input field accepts.

Worked example: factorising 2,431 by trial division

Trial division tests the primes in order until the quotient reaches 1. The bound is the square root of what is left: once a test prime passes the square root of the remaining quotient, that quotient is itself prime and the search stops.

Start with 2,431.

The quotient is 221. Now test 221 from the smallest prime again.

The quotient is 17, which is prime. The factorisation is 2,431 = 11 x 13 x 17. The check is one multiplication: 11 x 13 = 143, and 143 x 17 = 2,431.

The square root of 2,431 is 49.31, so a full search would test the 15 primes up to 47. This one stopped after five and six tests, which is typical. Numbers with small factors give them up early, and a number built from two large primes costs the most work.

Divisor counts from exponents

The exponents in the factorisation give the number of positive divisors. Add one to each exponent and multiply the results.

The last row is the test case worth running on any factoring tool. A prime has exactly two divisors, itself and 1, so a tool that returns the number unchanged and flags it as prime is behaving correctly.

Using the factorisation: GCF, LCM, and a simplified fraction

Two factorisations feed three common tasks. Take 360 = 2^3 x 3^2 x 5 and 504 = 2^3 x 3^2 x 7.

The two checks agree. 360 x 504 / 72 = 181,440 / 72 = 2,520, which is the lowest common multiple. Cancel the shared 2^3 and 3^2 from numerator and denominator and 360/504 reduces to 5/7, which is 0.714286 either way.

Why the search stops at the square root

If a number has a factor larger than its square root, it has a matching factor smaller than its square root, because the two factors multiply back to the number. Testing every prime up to the square root therefore finds every possible factor, and no further test can find anything new.

The cost of that search grows fast. For a number near 10^12 the square root is a million, and there are 78,498 primes below it. For a number near 10^20 the square root is ten billion, and no single machine finishes the job in useful time. RSA depends on that gap: multiplying two large primes takes microseconds, and separating the product does not. A 2,048 bit key is roughly 617 digits, far beyond trial division.

Sources

• Weisstein, E. W., Prime Factorization, MathWorld. https://mathworld.wolfram.com/PrimeFactorization.html. Accessed 2026-09-13.
• OEIS Foundation, sequence A000040, the prime numbers. https://oeis.org/A000040. Accessed 2026-09-13.

Also try these free tools:

• Prime Checker
• GCF Calculator
• LCM Calculator