Prime factorization calculator

Q: How do you find the prime factorization of a number?

Divide by the smallest prime that goes in, and repeat on the quotient until it reaches 1. For 360: 360 ÷ 2 = 180, ÷ 2 = 90, ÷ 2 = 45, ÷ 3 = 15, ÷ 3 = 5, and 5 is prime, so 360 = 2³ × 3² × 5. Only primes up to the square root of what is left need testing; if none divides it, the remainder is itself prime.

Q: Is 1 a prime number?

No. A prime has exactly two divisors, 1 and itself, and 1 has only one. Excluding 1 keeps factorizations unique: if 1 counted as prime, 6 could be written as 2 × 3, 1 × 2 × 3, 1 × 1 × 2 × 3 and so on. 1 is neither prime nor composite, and 2 is the smallest prime and the only even one.

Q: How do you find the number of divisors from the prime factorization?

Add 1 to each exponent and multiply. 360 = 2³ × 3² × 5¹, so it has (3 + 1)(2 + 1)(1 + 1) = 24 divisors, because each divisor uses 0 to 3 twos, 0 to 2 threes and 0 or 1 five. The sum of the divisors is a similar product: σ(360) = (2⁴ − 1)/1 × (3³ − 1)/2 × (5² − 1)/4 = 15 × 13 × 6 = 1,170.

Q: How can you tell if a large number is prime?

Trial division up to √n is far too slow for 20-digit numbers, so the Miller–Rabin test checks a handful of bases instead. Below 3.3 × 10²⁴, passing with the first 13 primes (2 to 41) as bases proves primality (Sorenson and Webster, 2015). 2⁶¹ − 1 = 2,305,843,009,213,693,951 passes and is prime; 2⁶⁷ − 1 fails and equals 193,707,721 × 761,838,257,287.

Q: Why does prime factorization matter in cryptography?

RSA encryption relies on multiplying two large primes being quick while factoring their product is impractically slow. NIST SP 800-57 rates a 2048-bit RSA modulus, about 617 decimal digits, as giving 112 bits of security. That is ten times the 60-digit limit here, and even within that limit Pollard's rho splits a number quickly only when one of its factors is fairly small.

Prime factorization of any whole number up to 60 digits, with a factor tree, a prime or composite verdict, its divisors and the nearest primes.

By Admin Drafted with AI writing toolsUpdated 29 October 2026Checked examples: 6

Prime factorization

2³ × 3² × 5

Prime or composite: Composite
Number of divisors: 24
Sum of divisors σ(n): 1,170
Previous prime: 359
Next prime: 367

360 = 2³ × 3² × 5, so it is composite. It has 24 divisors adding up to 1170. The nearest primes are 359 and 367.

Factor tree

Divisor pairs Rows: 12

Divisor	Paired divisor n ÷ d
1	360
2	180
3	120
4	90
5	72
6	60
8	45
9	40
10	36
12	30
15	24
18	20

How it's calculated S

Trial division by small primes
Divides by 2, 3.
Each prime is divided out as many times as it goes before moving on.
Prime factorization
$360 = 2^{3} \times 3^{2} \times 5$
Number of divisors
$d(n) = (3 + 1)(2 + 1)(1 + 1) = 24$
Sum of divisors
$\sigma(n) = \frac{2^{4} - 1}{2 - 1} \cdot \frac{3^{3} - 1}{3 - 1} \cdot \frac{5^{2} - 1}{5 - 1} = 1{,}170$
Nearest primes
$359 < 360 < 367$
Candidates are tested with the same Miller–Rabin check.

About the prime factorization calculator

By the fundamental theorem of arithmetic, every whole number above 1 is a product of primes in exactly one way, apart from order: 360 = 2³ × 3² × 5. The calculator divides out primes below 10,000 by trial division, splits larger composite factors with Brent's version of Pollard's rho method, and tests each factor for primality with a Miller–Rabin test on the first 13 prime bases, which is deterministic below 3.3 × 10²⁴ (Sorenson and Webster, 2015).

Simplifying fractions and radicals, finding common denominators, and number puzzles all start from a factorization. The exponents also count the divisors: 360 has (3 + 1)(2 + 1)(1 + 1) = 24 divisors that sum to 1,170, and the nearest primes are 359 and 367.

Numbers up to 60 digits are accepted, including expressions such as 2^67 − 1. At or above 3317044064679887385961981 a passing result is labeled “probable prime”. The 20 fixed bases used here do not provide a per-input error-probability guarantee.

How to find the prime factorization of a number

Divide by the smallest prime that goes in, repeat on the quotient, and stop when you reach 1. The primes you divided by, multiplied together, are the prime factorization: 84 ÷ 2 = 42, 42 ÷ 2 = 21, 21 ÷ 3 = 7 and 7 ÷ 7 = 1, so 84 = 2² × 3 × 7.

Every whole number above 1 has exactly one prime factorization, apart from the order of the factors. This is the fundamental theorem of arithmetic, and it is why two different factor trees for the same number always end on the same primes.

Prime factorization by repeated division

Work through 8712, using the smallest prime each time:

8712 is even: 8712 ÷ 2 = 4356, 4356 ÷ 2 = 2178 and 2178 ÷ 2 = 1089. That is three 2s.
The digits of 1089 add up to 18, so it divides by 3: 1089 ÷ 3 = 363 and 363 ÷ 3 = 121. That is two 3s.
121 is not divisible by 3, 5 or 7, but 121 = 11 × 11. That is two 11s.

So 8712 = 2³ × 3² × 11². Multiplying back checks it: 8 × 9 × 121 = 8712.

Divisibility tests save trial divisions. A number divides by 2 if its last digit is even, by 3 if its digit sum does, and by 5 if it ends in 0 or 5. It divides by 11 if its alternating digit sum does: 1 − 0 + 8 − 9 = 0 for 1089.

Perfect squares and cubes

A number is a perfect square exactly when every exponent in its factorization is even: 1,444 = 2² × 19² = 38², and 7,225 = 5² × 17² = 85². Halving each exponent gives the square root, so √1444 = 2 × 19 = 38.

When every exponent is a multiple of 3 the number is a perfect cube: 343 = 7³. Repeated primes multiply rather than add, so 7³ means 7 × 7 × 7 = 343, not 7 + 7 + 7.

Count and sum the divisors

If n = p₁ᵉ¹ × p₂ᵉ² × …, it has (e₁ + 1)(e₂ + 1)… positive divisors, because each divisor picks an exponent from 0 to e for every prime. So 8712 = 2³ × 3² × 11² has 4 × 3 × 3 = 36 divisors.

The sum of all divisors, σ(n), multiplies the sums of each prime's powers. For 2907 = 3² × 17 × 19 it is (1 + 3 + 9)(1 + 17)(1 + 19) = 13 × 18 × 20 = 4,680, and the sum includes 2907 itself.

Whole number	Prime factorization	Number of divisors	Sum of divisors
91	7 × 13	4	112
343	7³	4	400
361	19²	3	381
529	23²	3	553
2907	3² × 17 × 19	12	4680
13915	5 × 11² × 23	12	19152
16384	2¹⁴	15	32767

The square 361 = 19² has three divisors, 1, 19 and 361, because the middle pair 19 × 19 counts once. In the same way 16384 = 2¹⁴ has 15 divisors, the powers 2⁰ through 2¹⁴, not 14.

How to tell if a number is prime

A prime has exactly two divisors, 1 and itself. To test a number by hand, try prime divisors up to its square root. For 43, √43 ≈ 6.6, and none of 2, 3 or 5 divides it, so 43 is prime.

Some numbers only look prime: 91 = 7 × 13 and 361 = 19². The table gives the verdict and the neighboring primes for a few common checks:

Input	Verdict	Prime factorization	Previous prime	Next prime
1	Neither prime nor composite	1	—	2
31	Prime	31	29	37
43	Prime	43	41	47
47	Prime	47	43	53
91	Composite	7 × 13	89	97

1 is neither prime nor composite. It has only one divisor, and counting it as prime would break the uniqueness of factorizations, since 6 could then be 2 × 3 or 1 × 2 × 3.

Very large numbers

Numbers up to 60 digits can be factored, for example 10³⁰ + 1 = 61 × 101 × 3541 × 9901 × 27961 × 4188901 × 39526741. Large factors are split with Brent's version of Pollard's rho method.

Each factor is then proved prime with a Miller–Rabin test that is deterministic below about 3.3 × 10²⁴ (Sorenson and Webster, 2015). Above that bound a passing factor is labeled a probable prime.

A large composite factor that resists splitting is labeled composite, not split. The factorization is then incomplete, so the divisor count and sum are left out.

For every divisor of a number, not just its primes, use the factor calculator. For the factors two or more numbers share, the GCD and LCM calculator compares their factorizations.

Worked examples

360

Whole number: 360

Prime factorization: 2³ × 3² × 5
Prime or composite: Composite
Number of divisors: 24
Sum of divisors σ(n): 1,170
Previous prime: 359
Next prime: 367

Checked against: Trial division and divisor enumeration

Project Euler problem 3

Whole number: 600851475143

Prime factorization: 71 × 839 × 1471 × 6857
Number of divisors: 16

Checked against: Project Euler #3 (largest prime factor 6857)

Cole's factorization of 2^67 − 1

Whole number: 2^67-1

Prime factorization: 193707721 × 761838257287
Prime or composite: Composite
Number of divisors: 4

Checked against: F. N. Cole, 1903 (Bull. AMS 10:134)

97 is prime

Whole number: 97

Prime factorization: 97
Prime or composite: Prime
Number of divisors: 2
Sum of divisors σ(n): 98
Previous prime: 89
Next prime: 101

Checked against: Table of primes (OEIS A000040): 89, 97, 101

Questions

How do you find the prime factorization of a number?

Divide by the smallest prime that goes in, and repeat on the quotient until it reaches 1. For 360: 360 ÷ 2 = 180, ÷ 2 = 90, ÷ 2 = 45, ÷ 3 = 15, ÷ 3 = 5, and 5 is prime, so 360 = 2³ × 3² × 5. Only primes up to the square root of what is left need testing; if none divides it, the remainder is itself prime.

Is 1 a prime number?

No. A prime has exactly two divisors, 1 and itself, and 1 has only one. Excluding 1 keeps factorizations unique: if 1 counted as prime, 6 could be written as 2 × 3, 1 × 2 × 3, 1 × 1 × 2 × 3 and so on. 1 is neither prime nor composite, and 2 is the smallest prime and the only even one.

How do you find the number of divisors from the prime factorization?

Add 1 to each exponent and multiply. 360 = 2³ × 3² × 5¹, so it has (3 + 1)(2 + 1)(1 + 1) = 24 divisors, because each divisor uses 0 to 3 twos, 0 to 2 threes and 0 or 1 five. The sum of the divisors is a similar product: σ(360) = (2⁴ − 1)/1 × (3³ − 1)/2 × (5² − 1)/4 = 15 × 13 × 6 = 1,170.

How can you tell if a large number is prime?

Trial division up to √n is far too slow for 20-digit numbers, so the Miller–Rabin test checks a handful of bases instead. Below 3.3 × 10²⁴, passing with the first 13 primes (2 to 41) as bases proves primality (Sorenson and Webster, 2015). 2⁶¹ − 1 = 2,305,843,009,213,693,951 passes and is prime; 2⁶⁷ − 1 fails and equals 193,707,721 × 761,838,257,287.

Why does prime factorization matter in cryptography?

RSA encryption relies on multiplying two large primes being quick while factoring their product is impractically slow. NIST SP 800-57 rates a 2048-bit RSA modulus, about 617 decimal digits, as giving 112 bits of security. That is ten times the 60-digit limit here, and even within that limit Pollard's rho splits a number quickly only when one of its factors is fairly small.

About this calculator

\begin{gathered} n = p_1^{e_1} p_2^{e_2}\cdots p_k^{e_k} \\[6pt] d(n) = \prod (e_i + 1) \\[6pt] \sigma(n) = \prod \frac{p_i^{e_i+1} - 1}{p_i - 1} \end{gathered}

Sources

Hardy & Wright, An Introduction to the Theory of Numbers, §2.10 and §16.7 (divisor functions)
Sorenson & Webster (2015), Strong pseudoprimes to twelve prime bases
Brent (1980), An improved Monte Carlo factorization algorithm

Checked against references

This calculator includes 6 worked examples with independently sourced answers. They run in the test suite, and you can run them here too.

Put this calculator on your site

Paste this where you want the calculator to appear. It is free to use, it stays in step with corrections made here, and the credit line below it links back so your readers can find the full version.

Height

<iframe src="https://www.calcopenly.com/math/prime-factorization-calculator?embed=1"
        title="Prime factorization calculator by CalcOpenly"
        width="100%" height="820" loading="lazy"
        style="border:1px solid #d9dee2;border-radius:12px;max-width:680px"></iframe>
<p style="font:14px/1.6 system-ui,sans-serif;margin:.5rem 0 0">
  <a href="https://www.calcopenly.com/math/prime-factorization-calculator">Prime factorization calculator</a> by <a href="https://www.calcopenly.com/">CalcOpenly</a>
</p>

Preview the embed

Keep the credit line. It is the only condition, and it is what keeps these calculators free.

Factor tree

Trial division by small primes