Prime Factorization Calculator

How the prime factorization calculator works

A prime is a whole number greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, 13, … Every whole number from 2 up can be written as a product of primes in exactly one way, apart from the order of the factors. That product is its prime factorization. Enter a number and you get:

• the factorization in exponent form, such as 360 = 2³ × 3² × 5, and written out in full;
• whether the number is prime or composite (and why 0, 1 and negative numbers are neither);
• a factor tree that splits off the smallest prime at each step;
• how many divisors the number has, what they add up to, and the divisors themselves;
• the nearest primes below and above it;
• the working: which primes were divided out and how the last factor was shown to be prime.

Prime factors are the starting point for the greatest common factor and least common multiple (see the GCF and LCM calculator), for reducing fractions with the fraction calculator, and for simplifying radicals with the root calculator.

Trial division and the divisor formulas

Trial division. Divide by 2 as many times as it goes evenly, then by 3, then 5, 7, 11 and so on through the primes. You can stop as soon as the next prime squared is bigger than what is left: a number with no prime factor up to its square root is itself prime. That is why checking 97 only needs 2, 3, 5 and 7, since √97 ≈ 9.85.

Large numbers. Trial division up to the square root of an 18-digit number would take about a billion divisions, so above 10,000 the calculator switches methods. The Miller–Rabin test decides whether a number is prime; with the twelve bases 2 to 37 it gives no wrong answers below about 3.3 × 10²⁴ (Sorenson and Webster), far above this calculator's limit. Pollard's rho method then finds a factor of any composite that is left. All arithmetic is exact whole-number arithmetic, not floating point.

Divisors. If n = p₁^a₁ × p₂^a₂ × … × pₖ^aₖ, every divisor picks an exponent from 0 to a for each prime. That gives the count and the sum directly:

p₁ … pₖ

the different primes in the factorization

a₁ … aₖ

how many times each prime appears (its exponent)

Worked example: 360

1. Divide by 2 while it goes evenly: 360 ÷ 2 ÷ 2 ÷ 2 = 45. That is three 2s.
2. 45 is odd, so try 3: 45 ÷ 3 ÷ 3 = 5. That is two 3s.
3. 5 is prime (no prime up to √5 ≈ 2.24 divides it), so it is the last factor.
4. Collect them: 360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5.
5. Number of divisors: (3 + 1) × (2 + 1) × (1 + 1) = 4 × 3 × 2 = 24.
6. Sum of divisors: (2⁴ − 1) ÷ 1 × (3³ − 1) ÷ 2 × (5² − 1) ÷ 4 = 15 × 13 × 6 = 1,170.
7. Nearest primes: 361 = 19², 363 = 3 × 11² and 365 = 5 × 73 are composite, so the primes on either side are 359 and 367.

A prime. For 97, none of 2, 3, 5 or 7 divides it and 11² = 121 is already bigger than 97, so 97 is prime. It has two divisors, 1 and 97, and the nearest primes are 89 and 101.

A hard one. 999,999,866,000,004,473 has no prime factor below 10,000. Pollard's rho splits it into 999,999,929 × 999,999,937, two nine-digit primes, in a few milliseconds.

0, 1 and negative numbers

• 1 is not prime. If it were, factorizations would stop being unique (6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3 …). Its factorization is the empty product, and its only divisor is 1.
• 0 has no factorization. Every whole number divides 0 (0 = 0 × k), so it has infinitely many divisors and is neither prime nor composite. The smallest prime above it is 2.
• Negative numbers are not called prime or composite. The usual convention writes the sign as a factor of −1 and factors the absolute value: −360 = −1 × 2³ × 3² × 5. Divisor counts and nearest primes refer to the absolute value.
• 2 is the only even prime. Every other even number has 2 as a factor, which is why trial division starts there and then only tries odd numbers.

Limits

The calculator accepts whole numbers from −10¹⁸ to 10¹⁸. Above that, a number made of two large primes can take seconds to split in a browser, so it is not offered. Numbers with many divisors show the smallest 120 of them; the rest are those numbers' partners (n ÷ d). The written-out form is left out when a number has more than 24 prime factors. For decimals or fractions, factor the numerator and denominator separately.