Prime Factorization
Decompose any integer into its prime factors.
About the Prime Factorization
The prime factorisation calculator decomposes any integer greater than 1 into a product of prime numbers. Every positive integer greater than 1 has a unique factorisation into primes, a result known as the Fundamental Theorem of Arithmetic, first proved in modern form by Gauss in Disquisitiones Arithmeticae (1801, Article 16).
The tool uses trial division: it divides out factors of 2 first, then odd numbers from 3 up to the square root of the remaining value. Each prime factor is extracted as many times as possible. The loop stops once k squared exceeds the remaining value, because at that point any remaining factor must itself be prime.
Trial division is fast enough for inputs up to about 10^15 — the cube of 10^5 fits comfortably in the iteration budget. For larger inputs (RSA-sized semiprimes with hundreds of digits), no efficient classical algorithm is known, and integer factorisation is the basis of RSA cryptography per RFC 8017. The General Number Field Sieve is the asymptotically fastest known algorithm for very large integers.
The calculator returns both the list of prime factors and a compact factorisation string with exponents. For 360, the output is "2^3 x 3^2 x 5", which is the standard form used in number theory and physics.
How It Works
The algorithm iterates over candidate divisors and extracts each prime factor as many times as possible:
1. Divide n by 2 as many times as possible; record each 2.
2. For k = 3, 5, 7, 9, 11, 13, ... (odd numbers):
a. While k divides the remaining value, divide and record k.
b. Stop when k * k exceeds the remaining value.
3. If the remaining value is greater than 1, it is itself prime; record it.The reason we only need to check up to the square root is that if a number has a factor larger than its square root, it must also have a factor smaller than its square root. By the time we reach the square root, we have already extracted all small prime factors, so anything left must be prime.
The reason we only check odd candidates after 2 is that any even divisor would have been extracted by the initial factor-of-2 loop. A further optimisation is to check only numbers of the form 6k +/- 1 (since all other candidates are divisible by 2 or 3), but for inputs under 10^15 the simpler odd-only loop is already fast.
The tool reports the factorisation both as a flat list of prime factors (with repetition) and as a compact expression using exponents. For 360, the flat list is [2, 2, 2, 3, 3, 5] and the compact form is 2^3 x 3^2 x 5. Both forms are mathematically equivalent; the compact form is the canonical representation.
Worked Examples
Using the default value 360, the algorithm extracts three factors of 2 (360 / 2 = 180, 180 / 2 = 90, 90 / 2 = 45), then two factors of 3 (45 / 3 = 15, 15 / 3 = 5), then one factor of 5 (5 / 5 = 1). The factorisation is 2^3 x 3^2 x 5 = 8 * 9 * 5 = 360.
For a prime input such as 97, the algorithm checks odd divisors from 3 up to sqrt(97) (about 9.85), so 3, 5, 7, and 9. None of them divide 97, so the loop terminates and the remaining value 97 is itself prime. The factorisation is simply "97".
For a power of 2 such as 1024, the algorithm extracts ten factors of 2 in succession (since 1024 = 2^10), with no other factors. The compact form is 2^10. For 10^15 (one quadrillion), the loop runs about 31 million iterations in the worst case (sqrt of 10^15), which the tool handles in well under a second on modern hardware.
When to Use This Tool
Use the prime factorisation calculator when you need to:
Limitations & Disclaimer
This calculator uses trial division and is practical only for inputs up to about 10^15. Larger inputs may take a long time or fail outright; the tool rejects inputs above 10^15. The calculator works only on positive integers greater than 1. For cryptographic-size factorisation, use a dedicated algorithm such as the General Number Field Sieve. See our disclaimer for full details.
Frequently Asked Questions
What is the Fundamental Theorem of Arithmetic?
It states that every integer greater than 1 can be written uniquely as a product of primes, up to the order of the factors. Gauss proved it in modern form in Disquisitiones Arithmeticae (1801, Article 16). The theorem underpins much of number theory, including the simplification of fractions and the computation of GCDs and LCMs.
Why does the algorithm only check up to the square root?
Because if n has a factor larger than sqrt(n), the cofactor must be smaller than sqrt(n), so we would already have found it. Once we have extracted all small prime factors, any remaining value greater than 1 must itself be prime. This bound is what makes trial division practical for numbers up to about 10^15.
Can this calculator factorise very large numbers?
It works well up to about 10^15. For larger inputs, trial division becomes too slow: a 200-digit semiprime (the product of two 100-digit primes) would take longer than the age of the universe on current hardware. RSA cryptography (RFC 8017) relies on this difficulty.
Why are 0 and 1 not considered prime?
By definition, a prime number has exactly two distinct positive divisors: 1 and itself. The number 1 has only one divisor, so it is neither prime nor composite. The number 0 is divisible by every non-zero integer, so it is also neither. Excluding 1 from the primes is what makes the Fundamental Theorem of Arithmetic work.
How does factorisation relate to cryptography?
RSA encryption relies on the difficulty of factoring the product of two large primes. A 2048-bit RSA modulus is the product of two 1024-bit primes; factoring it in reasonable time is believed to require a quantum computer running Shor's algorithm (1994). Classical factorisation of such numbers is currently infeasible.
What is the difference between a prime and a composite number?
A prime number has exactly two positive divisors (1 and itself), while a composite number has more than two. The smallest prime is 2, the smallest composite is 4. Every composite number can be decomposed into a unique product of primes via the Fundamental Theorem of Arithmetic.
Last updated: September 9, 2026 · Author: HT99 Tools Editorial Team