Mathematics
Prime factorisation with steps
Type a whole number: get its prime factorisation with powers, the division ladder as done on paper, the list of divisors and the answer to whether the number is prime.
How to break a number into prime factors
Every whole number above 1 can be written in exactly one way as a product of primes: that is the fundamental theorem of arithmetic. To find them, divide by the smallest possible prime, 2, as long as you can, then by 3, by 5 and so on, writing the quotients in a column. For 360: 360 ÷ 2 = 180, ÷ 2 = 90, ÷ 2 = 45, ÷ 3 = 15, ÷ 3 = 5, ÷ 5 = 1, so 360 = 2³ × 3² × 5.
Almost everything else follows from the factorisation. The number of divisors is the product of the exponents each increased by one: for 360, 4 × 3 × 2 = 24. The HCF and LCM of two numbers come from comparing their factorisations, and a number is a perfect square when all its exponents are even.
For large numbers trial division becomes hopelessly slow: 30 digits would need billions of attempts. This calculator uses the Miller–Rabin test to recognise primes and Pollard's rho method to split composites, the same tools cryptography relies on.
Common mistakes
- Counting 1 as a prime: by definition a prime has exactly two divisors, and 1 has only one.
- Stopping at a factor that is not prime, as in 360 = 4 × 90: the factorisation is done only when every factor is prime.
- Trying divisors beyond the square root: if n has no divisor up to √n, it is prime.
Frequently asked questions
How can I tell whether a number is prime?
Check that no prime up to its square root divides it. For 97, whose root is about 9.8, testing 2, 3, 5 and 7 is enough: none divides it, so 97 is prime.
What is prime factorisation used for?
To find the HCF and LCM, to simplify fractions and surds, to count divisors. In cryptography, RSA's security rests precisely on how hard it is to factorise huge numbers.
What is Euler's totient?
φ(n) counts the numbers from 1 to n that share no factor with n. For a prime p it is p − 1; for 360 it is 96.
How this calculation works
n = p₁^a₁ × p₂^a₂ × … × pₖ^aₖ. Number of divisors = (a₁ + 1)(a₂ + 1)…(aₖ + 1). Sum of divisors = Π (pᵢ^(aᵢ+1) − 1) / (pᵢ − 1). Euler's totient φ(n) = Π pᵢ^(aᵢ−1)(pᵢ − 1). Method: trial division by the primes below 1000, a deterministic Miller–Rabin test and Pollard's rho factorisation in Brent's variant.
Related calculators
Factoring polynomials
Common factor, the factor theorem, special products and quadratics: factoring a polynomial step by step.
Synthetic division
Divides a polynomial by (x − a) and factors it.
GCD and LCM
Greatest common divisor and least common multiple with prime factorization.
Repeating decimal to fraction
From a recurring decimal to a fraction and from a fraction to a decimal, with the repeating block and the rule explained.