Prime Factorization Calculator

Type a whole number or an expression such as 2^71-1 and get its prime factorization in exponent form, a factor tree, the division steps, and the count, sum and full list of its divisors. Exact big-integer arithmetic handles numbers with hundreds of digits.

How to use the prime factorization calculator

1. Type a whole number, for example 360, or an expression such as 2^71-1 or 3*(10^12+7). You can use digits, +, -, *, ^ for powers and brackets. Spaces are ignored, so 1 000 000 works too.
2. Read the prime factorization in exponent form. It updates a moment after you stop typing; Enter calculates at once.
3. Below it you find the factor tree, the division steps and the list of all divisors, with their count and sum.
4. For a very large number a progress box appears. Stop or Esc cancels the search. If no factor turns up within 20 seconds, the tool shows what it has found so far and lets you keep searching for another minute.
5. The copy buttons copy the factorization or the divisor list. The small Slovenčina link under the input box switches the tool to Slovak, and English switches it back.

How it works

A prime number is a whole number greater than 1 whose only divisors are 1 and itself. The fundamental theorem of arithmetic says that every whole number greater than 1 is a product of primes in exactly one way, apart from the order of the factors. The calculator finds that product in three stages with exact big-integer arithmetic, so no digit is ever rounded.

1. Trial division. The number is divided by 2, 3, 5, 7 and every further prime up to 65,536, each as many times as it goes in. Only primes up to √n are needed: if n = a × b and both factors were larger than √n, their product would exceed n. So once p × p is bigger than what is left, what is left is prime.

2. Primality test. A large remainder is checked with the Miller–Rabin test using the 13 primes from 2 to 41 as bases. Below 3,317,044,064,679,887,385,961,981 (about 3.3 × 10²⁴) these bases are proven to give the right answer. Larger numbers must also pass a strong Lucas test; together this is the Baillie–PSW test, and no composite number that passes it has ever been found. Such factors are marked as probable primes.

3. Pollard's rho method (Brent's version). A composite remainder is split by repeating x → x² + c (mod n) and taking the greatest common divisor of n and the differences between the values. A prime factor p usually appears after about √p steps, so a 12-digit factor needs about a million steps, which takes well under a second in a browser.

From n = p₁^e₁ × p₂^e₂ × … × pₖ^eₖ the divisors follow. Each divisor uses every prime pᵢ with an exponent from 0 to eᵢ, so

d(n) = (e₁ + 1) × (e₂ + 1) × … × (eₖ + 1)
σ(n) = (p₁^(e₁+1) − 1)/(p₁ − 1) × … × (pₖ^(eₖ+1) − 1)/(pₖ − 1)

Here pᵢ are the different primes, eᵢ their exponents, d(n) the number of divisors and σ(n) the sum of all divisors, including 1 and n. The proper divisors add up to σ(n) − n; a number is perfect when that sum equals n, abundant when it is larger and deficient when it is smaller.

Examples

Example 1 – 360. 360 ÷ 2 = 180, 180 ÷ 2 = 90, 90 ÷ 2 = 45, 45 ÷ 3 = 15, 15 ÷ 3 = 5 and 5 ÷ 5 = 1, so 360 = 2³ × 3² × 5. It has (3 + 1)(2 + 1)(1 + 1) = 24 divisors with the sum 15 × 13 × 6 = 1,170. The proper divisors add up to 810, more than 360, so 360 is abundant.

Example 2 – 97. √97 ≈ 9.85, so only 2, 3, 5 and 7 need to be tried. None of them divides 97, so 97 is prime, with the two divisors 1 and 97.

Example 3 – 600,851,475,143. Trial division finds 600,851,475,143 = 71 × 839 × 1,471 × 6,857. Four different primes, each used once, give 2 × 2 × 2 × 2 = 16 divisors.

Example 4 – 2^71 − 1. The expression equals 2,361,183,241,434,822,606,847 (22 digits), and 2^71 − 1 = 228,479 × 48,544,121 × 212,885,833. All three factors are larger than 65,536, so trial division finds nothing; Pollard's rho method splits the number in well under a second.

Prime numbers, 1, 0 and negative numbers

1 is not prime. If it were, factorizations would not be unique: 6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3. It has no prime factors and one divisor. 0 has no prime factorization either, because every whole number divides it. For a negative number, factor its absolute value and put −1 in front: −360 = −1 × 2³ × 3² × 5.

Special forms can mislead: 2³ − 1 = 7, 2⁵ − 1 = 31 and 2⁷ − 1 = 127 are prime, but 2¹¹ − 1 = 2,047 = 23 × 89. In 1732 Euler showed that 2^32 + 1 = 641 × 6,700,417, and in 1880 Landry found that 2^64 + 1 = 274,177 × 67,280,421,310,721.

Factor trees and common mistakes

A factor tree splits a number into any two factors, then splits every composite factor again until only primes are left. Different first splits, such as 360 = 18 × 20 or 360 = 36 × 10, give different trees with the same prime leaves. The calculator splits each number into two factors of similar size, which keeps the tree short.

• Stopping at a composite leaf: 4, 9, 15 and 91 are not prime, so keep splitting.
• Dropping repeated factors: 2 × 3 × 5 is 30, not 360. Each prime appears as many times as it divides the number, which the exponent records.
• Trusting the last digit: odd numbers ending in 1, 3, 7 or 9 are often composite, for example 91 = 7 × 13 and 1,001 = 7 × 11 × 13.

Frequently asked questions

Is 1 a prime number?

No. A prime has exactly two different divisors, 1 and itself. The number 1 has only one, so it is neither prime nor composite.

When can I stop dividing?

When the quotient is 1. You can also stop as soon as the square of the next prime to try is larger than the current quotient: the quotient is then prime.

How large a number can it factor?

Up to 500 digits. Small factors are found almost at once, even in the 302-digit number 2^1000. The hard case is a number whose two largest prime factors are both big. Two 12-digit primes take well under a second; with two primes of about 16 digits the search reaches the 20-second limit, and two 20-digit primes would need half an hour or more.

What does "probable prime" mean here?

Factors above about 3.3 × 10²⁴ pass the Baillie–PSW test but are not formally proven prime, so they carry an asterisk.

Sources

• Sorenson J, Webster J (2017). Strong pseudoprimes to twelve prime bases. Mathematics of Computation 86(304): 985–1003. Finds the smallest number that fools the Miller–Rabin test for all 13 prime bases from 2 to 41: 3,317,044,064,679,887,385,961,981, the limit used above.
• Baillie R, Wagstaff SS Jr (1980). Lucas pseudoprimes. Mathematics of Computation 35(152): 1391–1417. The strong Lucas test and its combination with an ordinary probable-prime test, now called the Baillie–PSW test.
• Baillie R, Fiori A, Wagstaff SS Jr (2021). Strengthening the Baillie-PSW primality test. Mathematics of Computation 90(330). States that no odd composite number has been reported to pass the test.