Prime Factorization Calculator

Prime factorizations of common numbers

Numbers with many divisors

Miller–Rabin witness sets used for the prime test

How to find the prime factorization of a number by hand

1. Divide by the smallest prime that goes in. Try 2, then 3, 5, 7 and so on. 360 is even, so divide by 2: 360 ÷ 2 = 180. Keep dividing by the same prime while it still goes in: 180 ÷ 2 = 90, 90 ÷ 2 = 45.
2. Move to the next prime when it stops going in. 45 is odd, so try 3: 45 ÷ 3 = 15 and 15 ÷ 3 = 5. Then 5 is prime and the division ends.
3. Stop when the square of the prime passes what is left. You only need to try primes p with p × p no larger than the remaining number; if none goes in, what is left is prime. This is why 97 is prime: no prime up to 9 divides it.
4. Collect the primes and write exponents. The primes you divided out are 2, 2, 2, 3, 3 and 5, so 360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5. Draw the same split as a factor tree if you want a picture.
5. Get the divisor count from the exponents. Add 1 to each exponent and multiply: (3 + 1)(2 + 1)(1 + 1) = 24 divisors of 360.

Frequently asked questions

What is prime factorization?

It is writing a whole number greater than 1 as a product of primes. By the fundamental theorem of arithmetic every such number has exactly one prime factorization, apart from the order of the factors. 360 = 2³ × 3² × 5, and no other set of primes multiplies to 360.

How do I know if a number is prime?

A prime has exactly two divisors, 1 and itself. To check by hand, divide by every prime whose square is no more than the number: 97 has no divisor among 2, 3, 5 and 7, so it is prime, while 91 = 7 × 13 is not. The calculator uses the Miller–Rabin test, which is proven correct for every number below 3,317,044,064,679,887,385,961,981.

Is 1 a prime number?

No. A prime has exactly two divisors, and 1 has only one. Calling 1 prime would also break the uniqueness of prime factorization, because 6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3 and so on. 1 is neither prime nor composite; it is the empty product.

What is a factor tree?

A diagram that splits a number into two factors, then splits each composite factor again until every branch ends in a prime. Here 360 splits into 2 and 180, then 180 into 2 and 90, and so on to the leaves 2, 2, 2, 3, 3 and 5. The tool always splits off the smallest prime, so the tree has one shape for each number. The drawing has a text description and the same tree is given as a nested list for screen readers.

How do I count the divisors of a number?

Factor it, add 1 to each exponent and multiply. 60 = 2² × 3 × 5, so it has (2 + 1)(1 + 1)(1 + 1) = 12 divisors. The sum of the divisors is the product of (p^(e+1) − 1)/(p − 1) for each prime power: 60 gives 168. 12 has 6 divisors adding up to 28.

What is Euler’s totient function?

φ(n) counts the numbers from 1 to n that share no factor with n. From the factorization, φ(n) = n × the product of (1 − 1/p) over the distinct primes p. For 36 = 2² × 3² that is 36 × 1/2 × 2/3 = 12. For a prime p, φ(p) = p − 1: φ(97) = 96. It is used in RSA key generation and in modular arithmetic.

How does it find the factors of a big number?

It divides out every prime below 10,000 first, then tests what is left for primality with Miller–Rabin and, if it is composite, uses Pollard’s rho algorithm (Brent’s variant) to find a factor. That factors a number like 600851475143 = 71 × 839 × 1471 × 6857 instantly. Everything runs in a background thread in your browser, so the page stays responsive.

Why does it say “too hard to factor here” for some numbers?

Pollard’s rho takes about the square root of the smallest prime factor in steps, so a number made of two primes of about 14 digits each needs about ten million big-number steps. The tool gives each number a few seconds and then shows what it found so far. Numbers like that are exactly what RSA relies on being hard to factor; serious factoring uses methods such as the quadratic or number field sieve on many machines.

Is a very large result really prime?

Below 3,317,044,064,679,887,385,961,981 (about 3.3 × 10²⁴) the answer is proven, because the Miller–Rabin witness sets are known to have no exceptions there. Above that the tool tests 20 prime bases and labels a passing number “probable prime”: no number is known that passes all of them and is composite, but there is no proof. Composite answers are always certain, since a single failing witness proves a number composite.

How many primes are there up to 100 and up to 1,000,000?

There are 25 primes up to 100 and 78,498 up to 1,000,000, the largest of them being 999,983. The “Primes up to N” list uses the Sieve of Eratosthenes, which crosses out the multiples of each prime in turn, and shows the first 1,000 primes.

Which numbers are the next and previous prime?

They are the closest primes above and below the number you enter. For 360 they are 367 and 359. Prime gaps grow slowly (about the number of digits times 2.3 on average), so the search is quick even for 30-digit numbers.

How do I use prime factors to find the GCD or LCM?

Write both numbers in exponent form: 18 = 2 × 3² and 24 = 2³ × 3. The GCD takes each shared prime to the smaller exponent (2 × 3 = 6) and the LCM takes every prime to the larger exponent (2³ × 3² = 72).