Audited 26 May 2026·Last updated 27 Jul 2026·7 citations·Tier 1·0 uses

Prime Factorization Calculator

Free prime factorization calculator: factor any integer up to one billion into primes, with the unique factorization, prime count, sum of factors, and proof.

Prime Factorization Calculator

Integer to factor (n)Integer up to one billion. Enter any whole number n with 2 ≤ n ≤ 1,000,000,000 — the calculator returns the unique prime factorization of n together with how many prime factors it has, the smallest and largest of them, whether n itself is prime, and the sum of its prime factors.

Number of prime factors (with multiplicity)

The total number of prime factors of n counted with multiplicity — the number theorist's big-omega function Ω(n). For n = 60 = 2²·3·5 the count is 4 (two 2s, one 3, one 5). If you only want the count of *distinct* primes (the little-omega function ω(n)) the breakdown panel reports it alongside.

Largest prime factor

Smallest prime factor

Is n prime? (1 = yes, 0 = no)

Sum of prime factors (with multiplicity)

Background.

The Quanta prime factorization calculator takes any integer n between 2 and one billion and decomposes it into the unique product of prime numbers guaranteed by the Fundamental Theorem of Arithmetic. Enter 60 and it returns 2²·3·5. Enter 13,195 and it returns 5·7·13·29. Enter 1,000,000,007 — a popular cryptographic modulus — and it tells you that the number is itself prime, so its factorization is just 1,000,000,007. Alongside the factor list the calculator returns five derived quantities mathematicians and competitive programmers ask for most often: the total prime count counted with multiplicity (the big-omega function Ω(n) from analytic number theory), the largest prime factor, the smallest prime factor, a primality flag (1 if n is prime, 0 otherwise), and the sum of the prime factors with multiplicity (sopfr(n), sometimes called the integer logarithm). The factorization is unique — that uniqueness is the content of the Fundamental Theorem of Arithmetic, proved in essentially the form we use today by Euclid in Book VII of the Elements around 300 BCE and rigorously formalised by Gauss in Article 16 of the Disquisitiones Arithmeticae in 1801 — so however you order the factors and however you arrived at them, the answer the calculator gives is the only correct answer.

Under the hood the calculator runs deterministic trial division optimised for the input range. It strips out all factors of 2 first, then iterates over odd candidates d = 3, 5, 7, 9, … dividing n by d as many times as d divides cleanly and exiting as soon as d² exceeds the remaining quotient. The early-exit condition is the entire reason the algorithm is fast: if no prime factor up to √n has been found, then whatever is left of n must itself be prime, because every composite number has a prime factor no larger than its square root. For n ≤ 10⁹ that means at most about 31,623 trial divisions — a few microseconds in JavaScript — so every input in our range factors essentially instantly.

Beyond 10⁹ the picture changes dramatically. Trial division is O(√n), which means doubling the number of digits squares the work, and by the time n has 25 digits trial division is hopeless on any single machine. That is the entire reason public-key cryptography exists. The RSA cryptosystem, published by Rivest, Shamir, and Adleman in Communications of the ACM in 1978 and still the workhorse of TLS, SSH, and PGP, derives its security from exactly this asymmetry: it is computationally trivial to multiply two 1024-bit primes p and q together to form the public modulus n = pq, but factoring that n back into p and q is so hard that the current public record — RSA-250, a 250-digit (829-bit) modulus — was only achieved in 2020 after the equivalent of roughly 2,700 CPU-years using the general number field sieve, the asymptotically fastest known classical factoring algorithm. The 2048-bit moduli used in production HTTPS today are estimated to require many billions of times that work to factor on classical hardware. (Shor's algorithm reduces this to polynomial time on a fault-tolerant quantum computer, which is why NIST has been standardising post-quantum cryptography — ML-KEM and ML-DSA — since 2024.)

Prime factorization is also where you meet the Mersenne primes — primes of the form 2ᵖ − 1, where p must itself be prime — the family that has held the world record for largest known prime since Euclid noticed their connection to perfect numbers. As of 2024 the largest known prime is M₈₆,₀₂₁,₉₆₉ = 2⁸⁶⁸²¹⁹⁶⁹ − 1, a 41-million-digit number discovered by Luke Durant under the Great Internet Mersenne Prime Search.

This page covers all of that: how the algorithm works, why it is fast on small inputs and impossible on cryptographic ones, what the Fundamental Theorem of Arithmetic actually says, where prime factorization shows up outside maths class (RSA, hash table sizing, music theory's just intonation, integer-programming relaxations), and worked examples ranging from 60 to 13,195 to a primality verdict on a billion-scale candidate. Whether you arrived for homework, contest prep, a cryptography refresher, or just to see whether a particular integer is prime, the calculator above and the explainer below cover every variant of the question.

What is prime factorization calculator?

Prime factorization is the process of writing a positive integer n ≥ 2 as a product of prime numbers. A prime number is an integer greater than 1 whose only positive divisors are 1 and itself; the first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, … . Every integer n ≥ 2 either is itself prime, in which case its prime factorization is the trivial product n = n, or it is composite and can be written as a product of two or more primes (with repetition allowed). The Fundamental Theorem of Arithmetic states that this factorization is unique up to the order of the factors: there is exactly one multiset of primes that multiplies to give n. In the standard "canonical" form we collect equal primes into prime powers and list them in increasing order: 60 = 2²·3·5, 1,000 = 2³·5³, 720 = 2⁴·3²·5. The theorem has two ingredients: existence (every n ≥ 2 has *some* prime factorization, proved by strong induction — either n is prime and we are done, or n = ab with 1 < a, b < n, and by hypothesis a and b have factorizations whose concatenation is a factorization of n) and uniqueness (no number has two genuinely different factorizations, proved using Euclid's lemma: if a prime p divides a product ab then p divides a or p divides b). Euclid proved the existence half in Proposition 31 of Book VII of the Elements (c. 300 BCE) and proved Euclid's lemma in Proposition 30; the full uniqueness statement was first stated cleanly by Gauss in Article 16 of the Disquisitiones Arithmeticae in 1801. From the canonical factorization n = p₁^a₁ · p₂^a₂ · … · pₖ^aₖ every multiplicative number-theoretic function of n can be read off mechanically: the number of divisors d(n) = (a₁+1)(a₂+1)…(aₖ+1); the sum of divisors σ(n) = ∏i (pᵢ^(aᵢ+1) − 1)/(pᵢ − 1); Euler's totient φ(n) = n·∏i (1 − 1/pᵢ); the big-omega Ω(n) = a₁ + a₂ + … + aₖ (counted with multiplicity); the little-omega ω(n) = k (distinct primes only); the sum-of-prime-factors sopfr(n) = a₁·p₁ + … + aₖ·pₖ. The same factorization is the entry point to every gcd/lcm question (gcd takes the minimum exponent of each prime, lcm takes the maximum), to modular arithmetic, to Chinese-remainder reconstruction, and to public-key cryptography.

How to use this calculator.

Enter your integer n in the input field. Any whole number from 2 up to 1,000,000,000 is allowed — the upper bound is set by what trial division can do interactively in the browser. Decimals, negatives, zero, and one are rejected; the prime factorization of 1 is the empty product and is conventionally not asked, and primes are only defined for integers ≥ 2.
Read the primary result — the total number of prime factors of n counted with multiplicity — at the top of the results panel. This is the big-omega function Ω(n) from analytic number theory; for n = 60 it is 4 because 60 = 2·2·3·5 has four prime factors counted with multiplicity.
Read the full canonical factorization in the breakdown text below the primary value: it lists the primes in increasing order with their exponents, e.g. 60 = 2² · 3 · 5. If the "is prime?" output reads 1, the factorization is just n itself (n has no non-trivial factors).
Use the smallest prime factor to spot easy divisibilities at a glance: if it is 2 the number is even; if it is 3 the digit sum of n is divisible by 3; if it is 5 the number ends in 0 or 5. The largest prime factor is the answer to Project Euler problem 3 and is the harder quantity — it can be as small as 2 (for powers of two) or as large as n itself (when n is prime).
If you need the count of distinct primes rather than the count with multiplicity, look at the breakdown for the little-omega ω(n) value. The two functions agree exactly when n is squarefree (no prime appears with exponent ≥ 2) and diverge otherwise; 12 = 2²·3 has Ω = 3 but ω = 2.
For inputs larger than 10⁹ the calculator will refuse the value — trial division becomes too slow to run inline. For those cases use a dedicated computer-algebra system (SageMath, PARI/GP, Mathematica) which implements Pollard rho and the elliptic-curve method for medium-sized inputs and the general number field sieve for cryptographic-scale numbers.

The formula.

The calculator implements deterministic trial division with the standard optimisations. Given n ≥ 2 it does the following. First, while n is divisible by 2, divide out a factor of 2 and append 2 to the factor list. This terminates after at most ⌊log₂ n⌋ iterations (at most 30 for n ≤ 10⁹). After this loop the remaining n is odd. Second, iterate a candidate divisor d over odd numbers starting at 3: 3, 5, 7, 9, 11, 13, … . While d² ≤ n, do the following: while d divides n exactly, divide n by d and append d to the factor list; then increment d by 2 and continue. Note that the candidate d is not required to be prime — by the time the loop reaches d = 9 every factor of 9 (namely 3) has already been divided out, so 9 will never divide what is left of n, and the loop wastes only a single comparison. Skipping the multiples of 3 with a so-called 'wheel-2-3' (advancing d through 5, 7, 11, 13, 17, 19, 23, 25, …) would shave roughly a third off the iteration count but is not worth the implementation complexity at this scale. The termination condition d² > n is the heart of the optimisation: every composite integer m has a prime factor p ≤ √m, because if both factors of m = ab satisfied a, b > √m we would have ab > m, a contradiction. Therefore if no divisor up to √n has been found, whatever value of n remains must itself be prime, and the loop exits with that residual value appended to the factor list. Third, if after the loop the residual n is > 1, append it to the factor list as the final (and necessarily largest) prime factor. The full factor list is then in non-decreasing order by construction, and the canonical 'prime powers' form is obtained by run-length-encoding it. From the factor list the five reported outputs follow directly: primeCount = length of the factor list = Ω(n); largestPrime = last element; smallestPrime = first element; isPrime = 1 if length == 1 else 0; sumOfFactors = sum of the factor list = sopfr(n). The worst-case running time is O(√n) divisions, achieved when n is prime (every odd candidate up to √n is tried in vain). For n = 10⁹ that worst case is about 15,811 division operations — milliseconds in JavaScript, instant from the user's perspective. Beyond about 10¹² the O(√n) cost becomes painful interactively and serious factoring requires sub-exponential algorithms: Pollard rho for medium n (heuristic O(n¹ᐟ⁴)), the elliptic-curve method (running time governed by the size of the smallest prime factor of n, not n itself), and the general number field sieve (sub-exponential, currently best-known for cryptographic-scale moduli).

A worked example.

Example

Take n = 60. Trial division starts at d = 2: 60 / 2 = 30 (append 2), 30 / 2 = 15 (append 2). Now 15 is odd, so the 2-loop exits. Move to d = 3: 15 / 3 = 5 (append 3). 5 is not divisible by 3. Increment to d = 5. Now check the termination condition: d² = 25 > 5, so the loop exits early. The residual 5 is > 1, so append it to the factor list as the final prime. The factor list is [2, 2, 3, 5], which run-length-encodes to 60 = 2² · 3 · 5. From the factor list the calculator derives every reported output: Ω(60) = 4 (four primes counted with multiplicity), smallestPrime = 2, largestPrime = 5, isPrime = 0 (because Ω > 1), and sopfr(60) = 2 + 2 + 3 + 5 = 12. The distinct-prime count ω(60) reported in the breakdown is 3 (the three distinct primes 2, 3, 5). As a sanity check on the Fundamental Theorem of Arithmetic, every other way of factoring 60 collapses to the same multiset: 60 = 6 · 10 = (2 · 3)(2 · 5) = 2² · 3 · 5, or 60 = 4 · 15 = 2² · 3 · 5, or 60 = 12 · 5 = 2² · 3 · 5 — the order of discovery changes but the multiset {2, 2, 3, 5} is invariant. Contrast this with n = 1,000,000,007. Trial division grinds through every odd d from 3 up to ⌊√1,000,000,007⌋ = 31,622 without finding a divisor, exits the loop, and reports the residual 1,000,000,007 as a prime in its own right. That number is in fact prime — it is the modulus used in tens of thousands of competitive-programming problems precisely because it is prime, large enough that no modular collision is plausible, and small enough that products fit in a 64-bit integer.

n60

Frequently asked questions.

What is prime factorization and why is it unique?

Prime factorization is the process of writing a positive integer n ≥ 2 as a product of primes — for example 60 = 2 · 2 · 3 · 5. It is unique up to the order of the factors: there is exactly one multiset of primes whose product is n. This uniqueness is the Fundamental Theorem of Arithmetic. The proof has two parts. Existence is a straightforward induction: either n is prime (done) or n = ab with 1 < a, b < n, and by induction a and b have factorizations whose concatenation factors n. Uniqueness follows from Euclid's lemma — if a prime p divides a product ab, then p divides a or p divides b — applied repeatedly to compare two purported factorizations and show that they must agree multiset-for-multiset. Euclid proved both ingredients in Book VII of the Elements (Propositions 30 and 31) around 300 BCE; Gauss stated and proved the modern uniqueness theorem cleanly in Article 16 of the Disquisitiones Arithmeticae in 1801.

What algorithm does this calculator use?

Deterministic trial division with the standard optimisations. The algorithm strips out all factors of 2 first, then walks an odd candidate d = 3, 5, 7, 9, … through the integers, dividing the current n by d as many times as d divides it cleanly. The loop terminates as soon as d² exceeds the remaining n, because at that point any further factor of n would have to be ≥ d > √n, which by the contrapositive of the 'composite implies prime factor ≤ √n' lemma means n is itself prime. Trial division runs in O(√n) time — fast enough that any n up to 10⁹ factors in milliseconds in JavaScript, but hopeless on cryptographic-scale inputs. For numbers above about 10¹² you want Pollard rho, ECM, or the general number field sieve; see Knuth's TAOCP Volume 2 §4.5.4 for the comprehensive treatment.

Why does the calculator cap inputs at one billion?

Because trial division is O(√n), and 10⁹ is the largest power of ten for which the loop reliably finishes inside a single browser frame on a slow phone. At n = 10⁹ the worst case (n prime) requires about 15,811 candidate divisions — negligible. At n = 10¹² the worst case is about a million divisions — still tolerable on a desktop, sluggish on mobile. At n = 10¹⁸ it is a billion divisions — seconds of unresponsiveness. Cryptographic moduli are 2048 bits, or about 10⁶⁰⁸, where trial division would take longer than the age of the universe. For anything above 10⁹ use a dedicated computer-algebra system: SageMath, PARI/GP, and Mathematica all implement Pollard rho, the elliptic-curve method, the quadratic sieve, and the general number field sieve, each suited to a different size range.

How is prime factorization used in cryptography?

Public-key cryptography — specifically the RSA cryptosystem, published by Rivest, Shamir, and Adleman in 1978 — derives its security from the hardness of factoring. The setup picks two large secret primes p and q (typically 1024 bits each), publishes their product n = pq as part of the public key, and uses the fact that anyone can multiply p and q together cheaply but no one without the private key can factor n back into p and q. The largest RSA modulus factored to date — RSA-250, a 250-digit number — fell in February 2020 after about 2,700 CPU-years of work using the general number field sieve, the asymptotically fastest known classical factoring algorithm. Production HTTPS uses 2048-bit RSA, which is estimated to require many billions of times that effort on classical hardware. Shor's algorithm (1994) reduces factoring to polynomial time on a fault-tolerant quantum computer, which is why NIST began standardising post-quantum cryptography (ML-KEM / Kyber, ML-DSA / Dilithium) in 2024 — the assumption that factoring will remain hard is no longer safe on the multi-decade horizon.

What is a Mersenne prime?

A Mersenne prime is a prime number of the form M_p = 2^p − 1, where the exponent p must itself be prime (this is a necessary but not sufficient condition: 2¹¹ − 1 = 2047 = 23 · 89 is composite even though 11 is prime). Mersenne primes are easier to test for primality than generic integers thanks to the Lucas–Lehmer test (1856 / 1930), and they are deeply tied to the perfect numbers — Euclid proved in Elements IX.36 that if 2^p − 1 is prime then 2^(p−1)(2^p − 1) is perfect, and Euler proved in the 18th century that every even perfect number has this form. Mersenne primes have held the record for largest known prime almost continuously since Euclid. As of December 2024 the largest known prime is M_82,589,933 = 2^82,589,933 − 1, a 41-million-digit number found by Luke Durant through the Great Internet Mersenne Prime Search (GIMPS), a distributed-computing project that has discovered all of the largest known primes for thirty years.

What is the difference between Ω(n) and ω(n)?

Ω(n) (big omega) counts the prime factors of n with multiplicity; ω(n) (little omega) counts only distinct primes. For n = 60 = 2² · 3 · 5 the big-omega is Ω(60) = 4 (two 2s, one 3, one 5) and the little-omega is ω(60) = 3 (the three distinct primes 2, 3, 5). The two agree exactly when n is squarefree (no prime appears with exponent ≥ 2). Both are additive arithmetic functions — they satisfy f(mn) = f(m) + f(n) whenever gcd(m, n) = 1 — and both feature in classical results: the Erdős–Kac theorem (1940), one of the founding results of probabilistic number theory, states that ω(n) is approximately normally distributed with mean and variance both close to log log n. The calculator returns Ω(n) as its primary 'prime count' output and reports ω(n) in the breakdown.

How can I tell if a number is prime quickly?

For small n, trial division up to √n is fast and conclusive: if no integer between 2 and ⌊√n⌋ divides n, then n is prime. The Quanta calculator does exactly this and returns 1 in the 'is prime?' output when n has only one prime factor (itself). For larger n probabilistic primality tests are dramatically faster. The Miller–Rabin test (Rabin 1980, based on Miller's 1976 deterministic test) certifies primality with probability of error at most 4^(−k) after k randomly chosen witnesses; with 40 witnesses the error probability is below 10^(−24), far below the chance of a cosmic-ray bit flip. For n < 3.3 × 10¹⁴ a fixed set of seven Miller–Rabin witnesses is provably deterministic, which is how production cryptographic libraries (OpenSSL, BoringSSL, Java's BigInteger.isProbablePrime) decide primality. For arbitrary-size n with a strict proof requirement, the AKS algorithm (Agrawal, Kayal, Saxena 2002) gives a deterministic polynomial-time primality test — a landmark result — though it is slower in practice than Miller–Rabin with sufficient witnesses.

What happens to performance for numbers larger than 10⁹?

Trial division becomes increasingly impractical because its running time is Θ(√n / log n) divisions. Doubling the number of digits squares the work. At n = 10¹⁸ — a 19-digit number, larger than a signed 64-bit integer can hold — trial division needs about 10⁹ operations, which takes tens of seconds in JavaScript. At n = 10³⁰ it is hopeless on any single machine. Real factoring at scale uses Pollard rho (Pollard 1975), which is heuristic O(n¹ᐟ⁴) and is the workhorse for numbers up to about 25 digits; the elliptic-curve method (Lenstra 1987), whose running time depends on the size of the *smallest* prime factor rather than n itself and is ideal for numbers with at least one moderately small factor; the quadratic sieve (Pomerance 1985); and the general number field sieve (Pollard, Lenstra, Lenstra, Manasse, Pomerance 1993), which is sub-exponential and currently the fastest known algorithm for cryptographic-scale numbers. The asymptotic complexity of GNFS is exp(((64/9)^(1/3) + o(1)) (ln n)^(1/3) (ln ln n)^(2/3)), which is much faster than trial division but still far too slow on 2048-bit RSA moduli.

Why is prime factorization important beyond cryptography?

It is the foundation of every multiplicative question in number theory. Once you have the canonical factorization of n you can read off the number of divisors, the sum of divisors, Euler's totient, the Liouville function, and the Möbius function mechanically. The greatest common divisor and least common multiple of two integers come straight from the prime-power minimum and maximum across their factorizations. In computer science prime factorization underlies the Chinese Remainder Theorem (used in fast modular arithmetic and in the standard implementation of RSA decryption), the structure of finite cyclic groups (whose orders factor uniquely), and hash table sizing (Java's HashMap and Python's dict avoid table sizes with small prime factors to reduce clustering). In music theory, 'just intonation' is the system in which musical intervals correspond to small-integer frequency ratios; the prime factorization of those ratios distinguishes the syntonic and Pythagorean commas. In chemistry, balancing reactions reduces to a linear-algebra problem over the rationals whose denominators come from prime factorizations of the coefficients. Anywhere multiplication is the natural operation, prime factorization is the right lens.

Is there a closed-form formula for the n-th prime?

No — not in any practically useful sense. There is no elementary formula p_n = f(n) that returns the n-th prime in time polynomial in n. There are exotic formulas (Mills's constant, Willans's 1964 prime-generating formula) but they either depend on constants that are themselves defined in terms of the primes or evaluate by exhaustive search disguised as algebra. What we do have is the Prime Number Theorem, proved independently by Hadamard and de la Vallée Poussin in 1896, which gives the asymptotic density: π(x), the count of primes up to x, satisfies π(x) ~ x / ln(x). Equivalently the n-th prime p_n is asymptotically n · ln(n). This is enough to estimate where to look but not to compute. Practical computation of primes is done by sieve methods: the sieve of Eratosthenes (ca. 240 BCE) finds all primes up to N in O(N log log N) time, and modern variants (Atkin's sieve, segmented sieves) push the constants down further. The Riemann Hypothesis, if true, would sharpen the error term in the Prime Number Theorem to O(√x · log x); it remains the most important open conjecture in number theory and one of the Clay Mathematics Institute's seven Millennium Prize Problems.

References& sources.

Related calculators

LCM and GCD Calculatornum Percentage Calculatorper Mean, Median, and Mode Calculatorsta Standard Deviation Calculatorsta Quadratic Equation Solveralg

In this category

Embed

Quanta Pro

Paid features are coming later.

All 313 calculators remain free
No billing is enabled

Coming soon