Prime Factorization & Factors Calculator

About the Prime Factorization & Factors Calculator

Type a whole number — or an expression such as 2^32 + 1 or 10! − 1 — to see its prime factorization as prime powers (360 = 2³ × 3² × 5), worked out two ways: as a factor tree and as a division ladder. Below that you get every factor in order, the factor pairs, the number and the sum of the factors, Euler’s totient, and what kind of number it is: prime or composite, perfect, abundant or deficient, square-free, a perfect square or cube.

Small prime factors are found by trial division; what is left is split with Pollard’s rho method in Brent’s version, in a background thread, so the page never freezes. That finds prime factors of up to about 15 digits within seconds, even in numbers with hundreds of digits. If a part cannot be split in time, the page says so, shows the factors it did find, and lets you keep trying for up to a minute.

Common uses

• Homework on prime factorization, factor trees, the ladder method, factors and multiples.
• Finding all the factors of a number — for example, to simplify a fraction or a square root, or to find every way of arranging items in equal rows.
• Checking number properties: perfect, abundant and deficient numbers, square-free numbers, perfect powers.
• Factoring test values for programs, such as 2^64 + 1 or products of large primes.

How the factors are found

• Trial division by every prime up to 1,000,000 removes the small factors. If what remains is less than the square of the last prime tried, it must itself be prime.
• Each remaining part is tested for primality: deterministic Miller–Rabin below 3.3 × 10²⁴ (a proof in that range) and Baillie–PSW above it, so larger prime factors are labelled probable primes.
• A composite part is checked for being a perfect power, then split with Pollard’s rho method (Pollard 1975), using Brent’s faster way of detecting the cycle (Brent 1980). Rho needs about √p steps to find a prime factor p, which is why factors of up to about 15 digits come out quickly and much larger ones may not be found at all.

Factor counts and sums from the prime factorization

If n = p₁^a₁ × p₂^a₂ × … × p_k^a_k, then:

• Number of factors: (a₁ + 1)(a₂ + 1)…(a_k + 1). For 360 = 2³ × 3² × 5¹ that is 4 × 3 × 2 = 24.
• Sum of factors σ(n): the product of (p^(a+1) − 1) ÷ (p − 1) for each prime. For 360: 15 × 13 × 6 = 1,170.
• Euler’s totient φ(n), the count of numbers from 1 to n that share no factor with n: n × (1 − 1/p₁) × (1 − 1/p₂) …. For 360: 360 × ½ × ⅔ × ⅘ = 96.

The sum of the proper factors (all except n itself) decides the type: equal to n makes it perfect (6, 28, 496, 8,128), more than n abundant (12, 18, 20 …) and less than n deficient (every prime, for example). A number is square-free when no prime appears twice, and a perfect square when every exponent is even.

Factor tree or division ladder?

Both give the same answer — every whole number above 1 has exactly one prime factorization (the fundamental theorem of arithmetic). A factor tree splits a number into any two factors and keeps splitting until only primes are left; the balanced style picks the pair closest to the square root, which keeps the tree short. The division ladder (or “upside-down division”) divides by the smallest prime again and again, so the primes come out in order down the left side.

Limitations

• Numbers can have up to 1,000 digits, but a number whose prime factors all have more than about 15–20 digits may not be fully factored — the page shows the factors it found and marks the rest as composite. Breaking a product of two very large primes (as in an RSA key) is beyond any browser tool.
• Prime factors above 3.3 × 10²⁴ are probable primes (Baillie–PSW, with no known counterexample), not proven primes.
• All factors and factor pairs are listed when there are at most 10,000 of them; the page shows the first 2,000 and the download has the rest. The factor tree is drawn for up to 40 prime factors.

Privacy

Everything happens in your browser. What you enter or open here is not uploaded or stored by MySmartCoPilot.