Prime Factor Calculator

The Prime Factor Calculator decomposes any positive integer n into its prime building blocks and derives three classical arithmetic functions on n in a single pass: the divisor count τ(n), the sum of divisors σ(n), and Euler's totient φ(n). The calculator uses trial division up to ⌊√n⌋ and falls back to JavaScript BigInt for integers larger than 2⁵³ (~9.0×10¹⁵), so it works comfortably on numbers up to roughly 10²⁵ without precision loss.

This is the standard number-theoretic preprocessing step for problems in cryptography (RSA modulus checks, perfect power detection), combinatorics (counting divisors for lattice sums), and theoretical competition math (project Euler, IMO shortlist). The tool also shows the exact trial-division step trace, every divisor it tried, whether it divided cleanly, and the running remainder, so you can audit the result by eye.

How to Use the Prime Factor Calculator

1. Type a positive integer in the input box (1, 12, 360, 9973, anything up to ~10²⁵). Whitespace, commas, and a leading "+" are stripped automatically.
2. Click "Factorise" (or press Enter). The result panel updates immediately.
3. Read the result panel, classification (unit, prime, or composite), canonical form p1^a1 × p2^a2 × ..., factor pairs pᵢ^aᵢ, then the three arithmetic functions τ, σ, and φ with their formulas expanded inline so you can check the work.
4. Scroll the trial-division trace (sticky-header table) to see every divisor attempt. Rows highlighted in yellow produced a factor; rows with the green ★ are the final remainder-prime that the loop left behind.
5. (Optional) Use a preset from the quick-presets strip to load a known input (17, 60, 100, 360, 2310, 9973, 10⁹+7) and verify the output matches reference values.
6. Reset clears the input and the panel.

The mode (Number or BigInt) is decided automatically from the input length: inputs ≤ 16 digits or ≤ 2⁵³ use the fast Number path; longer inputs use the BigInt path which can handle inputs of tens of digits.

The Math

The Fundamental Theorem of Arithmetic

Every integer n > 1 can be written uniquely (up to ordering of the primes) as a product of primes:

$$ n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_k^{a_k} $$

This is the Fundamental Theorem of Arithmetic, proved by Euclid and sharpened over the centuries (Hardy & Wright §1). The exponent vector (a₁, a₂, ..., a_k) is unique once the primes are ordered, there is exactly one way to write 60 = 2² · 3 · 5, and no other.

Trial division

The simplest algorithm to find the factorization is trial division: test each integer d = 2, 3, 4, ... up to ⌊√n⌋. For each d, divide out as many times as possible and record the exponent. Any leftover n' > 1 at the end is itself a prime, and is guaranteed to be the largest prime factor of n, because if a larger prime existed it would have been discovered when its smaller partner left a cofactor.

This algorithm is exact for any n that fits in memory, and for n ≤ 10¹⁵ it runs in under a second on any modern device. Two optimizations help:

• Skip even d after handling d = 2. That halves the candidate set.
• Stop at √remaining. Once d² > n, every prime ≤ n has either been found or is n itself.

The total cost is bounded by the sum over primes p ≤ √n of O(logₚ(n)) divisions, which is roughly O(√n / log n) operations, fine for any practical input.

Divisor count τ(n)

If n = Π pᵢ^aᵢ, then the number of positive divisors of n is

$$ \tau(n) = (a_1 + 1)(a_2 + 1)\cdots(a_k + 1). $$

The reasoning: for each prime pᵢ, the divisor may use pᵢ⁰, pᵢ¹, …, or pᵢ^aᵢ, that's (aᵢ + 1) choices, and the choices are independent across distinct primes. So τ(n) is a multiplicative function that multiplies (aᵢ + 1) across all prime-power factors.

Examples:

• 60 = 2² · 3 · 5 → τ = (2+1)(1+1)(1+1) = 12 divisors.
• 100 = 2² · 5² → τ = (2+1)(2+1) = 9 divisors.
• A perfect k-th power n = m^k has k divisors when τ(m) = k, which makes n = m^(k-1) a perfect power.

Sum of divisors σ(n)

$$ \sigma(n) = \sum_{d \mid n} d = \prod_i \frac{p_i^{a_i + 1} - 1}{p_i - 1}. $$

The right-hand form comes from summing the geometric series 1 + pᵢ + pᵢ² + ... + pᵢ^aᵢ = (pᵢ^(aᵢ+1) − 1)/(pᵢ − 1) for each prime and multiplying across distinct primes (σ is multiplicative and the terms are coprime).

Examples:

• σ(60) = σ(2²) · σ(3) · σ(5) = 7 · 4 · 6 = 168.
• σ(100) = σ(2²) · σ(5²) = 7 · 31 = 217.
• σ(n) = 2n marks a perfect number (smallest example: 6 = 1 + 2 + 3).

Euler's totient φ(n)

Euler's totient φ(n) counts integers in {1, 2, ..., n} that are coprime to n. For a prime power:

$$ \varphi(p^a) = p^a - p^{a-1} = p^{a-1}(p - 1). $$

Across distinct primes (using multiplicity-multiplied coprimality):

$$ \varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right). $$

Examples:

• φ(60) = 60 · (1/2) · (2/3) · (4/5) = 16. (The 16 integers ≤ 60 coprime to 60 are 1, 7, 11, 13, …, 59.)
• φ(100) = 100 · (1/2) · (4/5) = 40.
• φ(p) = p − 1 for prime p (Fermat's little theorem setting).

φ(n) is the order of the multiplicative group (ℤ/nℤ)✶ and is foundational for RSA: if gcd(e, φ(n)) = 1 then e has a multiplicative inverse d mod φ(n), and m^(e·d) ≡ m (mod n), the RSA correctness statement.

BigInt mode (n > 2⁵³)

For integers larger than Number.MAX_SAFE_INTEGER (~9.0×10¹⁵), IEEE-754 doubles cannot represent every integer exactly. JavaScript's BigInt primitive (ECMAScript 2020+) represents integers of arbitrary size with a single-bit precision guarantee. The calculator uses the BigInt path whenever the input has more than 16 digits or exceeds 2⁵³, and computes σ, τ, and φ in BigInt arithmetic so the result is always exact.

For the trade-off: BigInt arithmetic is several times slower than Number arithmetic, and BigInt(p^(a+1)) for very large p can produce allocations in the kilobyte range. For inputs around 10²⁵ the calculator returns in under a few seconds; inputs around 10³⁰ are still tractable but start to feel slow. There is no hard upper bound, just an effective one driven by patience.

Worked Examples

Example 1: 60

Factorisation: 60 = 2² · 3 · 5 τ(60) = 12: divisors are 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60. σ(60) = 168: 1 + 2 + 3 + 4 + 5 + 6 + 10 + 12 + 15 + 20 + 30 + 60 = 168. φ(60) = 16: the 16 integers ≤ 60 coprime to 60, {1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59}.

Example 2: A prime, 17

17 is tested against d = 2, 3, 4 (skipped to 5 since √17 ≈ 4.12). None divide evenly. By trial division 17 is prime. The canonical form is 17¹, τ = 2, σ = 18, φ = 16. The trial-division trace ends on the green ★ row marking the remainder prime.

Example 3: A perfect square, 100

100 = 10² = (2 · 5)² = 2² · 5². Trial division: 2 divides twice, 3, 5, 7 don't divide (4, 9 are skipped as 2-multiples), but after the divisor 2 we have a working value of 25, and 5² divides out cleanly giving the final remainder 1.

• τ(100) = (2+1)(2+1) = 9 divisors: 1, 2, 4, 5, 10, 20, 25, 50, 100.
• σ(100) = 217.
• φ(100) = 40 (= 100 · (1/2) · (4/5) = 100 · 2/5 = 40).

Example 4: The primorial, 2310

2310 = 2 · 3 · 5 · 7 · 11 = the product of the first five primes ("primorial 11#"). Trial division yields five distinct prime factors, all with exponent 1. The calculator reports:

• τ(2310) = 2⁵ = 32 divisors.
• σ(2310) = 3 · 4 · 6 · 8 · 12 = 6912.
• φ(2310) = 2310 · (1/2)(2/3)(4/5)(6/7)(10/11) = 480.

Primorials are maximally composite at their size and are the canonical example for showing how multiplicative functions telescope.

Example 5: A large-prime-squared, 9973²

9973 is itself a 4-digit prime (verified by trial division up to ⌊√9973⌋ ≈ 99.8). Squaring gives 9973² = 99 460 729. The factorization is (9973)² = 9973², with τ = 3 (divisors: 1, 9973, 99 460 729), σ = 1 + 9973 + 99 460 729 = 99 470 703, φ = (9973 − 1) · 9973 = 9972 · 9973 = 99 450 756. This case demonstrates the BigInt-adjacent Number path: 9973² has 8 digits and still fits comfortably in 2⁵³, so the fast path is used.

Example 6: BigInt mode, ~10²⁰

A 21-digit input such as 123456789012345678901 forces the BigInt path. Trial division up to √n ≈ 3.5×10¹⁰ runs through all primes ≤ 3.5×10¹⁰ (≈ 1.9 billion divisions worst-case, but most numbers won't be that smooth). In practice a 21-digit input gives a factorization in a few seconds, with σ(n) and φ(n) returned as BigInt strings when they exceed Number precision.

Where the Concept Shows Up

Cryptography (RSA, Diffie-Hellman, elliptic curves)

RSA modulus generation requires two random primes p and q of ~1024 bits each; n = pq, and the public exponent e must be coprime to φ(n) = (p − 1)(q − 1). Knowing the prime factorization of n is therefore equivalent to breaking RSA, there's no known polynomial-time algorithm to factor a 2048-bit RSA modulus, and the security of RSA rests on that difficulty. φ(n) and τ(n) are the two quantities a factoring algorithm ultimately recovers.

Euler's totient φ(n) generalises across all of public-key cryptography: every cryptosystem whose security reduces to "factor n" or "compute discrete log mod n" feeds on totient values.

Number theory and competition math

Counting divisors (τ), summing divisors (σ), and computing totients (φ) are core skills for math olympiads. The identities τ(p^a) = a + 1, σ(p^a) = (p^(a+1) − 1)/(p − 1), φ(p^a) = p^(a−1)(p − 1) appear in nearly every Project Euler problem involving a sequence.

Computer science (hash tables, lattices)

Hash-table bucket sizing uses prime moduli to spread keys uniformly. Computing τ(n) tells you how many residue classes are non-units mod n; computing φ(n) tells you the multiplicative group order, which determines when Blum integers (n with exactly two prime factors ≡ 3 mod 4) are useful for the Blum-Goldwasser cryptosystem.

Engineering and physics

Compound-interest calculations and decay constants involve products over prime-power factors of state-transition matrices. Semiconductor doping profiles sum over σ(p^a) doping ions per unit cell. Lattice sums in solid-state physics reduce to multiplicative functions of the index n.

Common Mistakes

Mistaking 1 for a prime

1 is not prime. It's the multiplicative identity, and calling it a prime breaks uniqueness of factorization. Most definitions of "prime" exclude 1 explicitly (Hardy & Wright §1: "a prime is a positive integer > 1 whose only positive divisors are 1 and itself"). The calculator handles 1 correctly: empty prime list, τ = 1, σ = 1, φ = 1.

Confusing "prime" with "prime power"

A prime power is a number of the form p^a with a ≥ 1 (so all primes are also prime powers, with a = 1). But many tools distinguish them. This calculator uses the standard textbook definition: a prime has only two divisors (1, itself); a prime power has τ = a + 1 divisors. The calculator always reports exponent = 1 for primes.

Using floating-point for large numbers

JavaScript's Number is IEEE-754 double precision: integers > 2⁵³ − 1 = 9007199254740991 cannot all be represented exactly. For an input like 9007199254740993, parseInt(n, 10) + 1 gives 9007199254740994 (off by one), which then fails every divisibility test in subtle ways. The BigInt path is mandatory for any input > 16 digits.

Trial division efficiency at scale

Trial division is fine for n ≤ 10¹⁵ but doesn't scale to RSA-scale inputs (10⁶⁰⁰ or more). For those, modern factoring uses the General Number Field Sieve, with sub-exponential complexity ~ exp((log n)^(1/3) (log log n)^(2/3)). Trial division is the "right" pedagogical tool but the wrong industrial tool, use this calculator for homework, not for cryptanalysis.

Forgetting the remainder prime

A common off-by-one bug in trial division is forgetting the case where the loop ends with a remainder > 1. That remainder is itself a prime (the largest prime factor of n), and must be recorded. The calculator handles this with the green ★ row at the bottom of the step table.

Reading the totient formula wrong

φ(n) = n × Π(1 − 1/p) is over distinct primes, not over all prime-power factors. A common error is computing (a + 1) terms (one per exponent) instead of k terms (one per distinct prime). For p^a, the formula gives p^a · (1 − 1/p) = p^(a−1)(p − 1), which equals the exponent-multiplied form. The calculator applies it correctly using only factors.map(f => f.p) (distinct primes, ignoring a).

Tips for Accurate Factoring

Pick input mode to match the input

Inputs ≤ 16 digits use the Number path and complete in milliseconds. Inputs of 17 to 25 digits use BigInt and complete in seconds; longer inputs are supported but will be slow. If you need results quickly, prefer factoring a small auxiliary number rather than the full large one when possible.

Verify with multiplicative identities

After factoring, cross-check τ, σ, and φ against simple identities: τ(p^a) = a + 1, σ(p) = p + 1 for primes, φ(p) = p − 1 for primes. The calculator exposes these identities by expanding (aᵢ + 1) and (1 − 1/pᵢ) in the result panel.

Use the step trace for primes

To convince yourself an integer is prime, watch the trial-division trace fill the entire √n. For a 7-digit prime such as 9973, that's 100 test divisors with no hits, a clean visual proof.

Watch the σ/φ ratio

For composite n, σ(n) is often much larger than φ(n) (e.g. σ(60) = 168 vs φ(60) = 16). For prime n they are close: σ(p) = p + 1, φ(p) = p − 1. The ratio σ(n)/φ(n) gives a quick sanity check on the classification.

Frequently Asked Questions

What does "prime factorisation" mean? Prime factorisation (or prime decomposition) is the unique representation of an integer n > 1 as a product of primes, with each prime raised to its appropriate exponent. For example, 60 = 2² · 3 · 5. Every positive integer (other than 1) has exactly one such representation, by the Fundamental Theorem of Arithmetic. This calculator computes that representation and three arithmetic functions derived from it: divisor count τ(n), sum of divisors σ(n), and Euler's totient φ(n).

What is trial division? Trial division is the simplest factoring algorithm: test d = 2, 3, 4, ... up to ⌊√n⌋. For each d that divides n cleanly, divide it out as many times as possible and record the exponent. Any leftover n′ > 1 at the end is itself a prime. Trial division is exact and provably correct; for n ≤ 10¹⁵ it's also practical in time.

How is τ(n) computed? The divisor-count function τ is multiplicative and satisfies τ(p^a) = a + 1 for a prime power. So if n = Π pᵢ^aᵢ then τ(n) = Π (aᵢ + 1). Example: 60 = 2² · 3 · 5 gives τ(60) = (2+1)(1+1)(1+1) = 12. The 12 divisors of 60 are 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60.

How is σ(n) computed? The sum-of-divisors function σ is multiplicative and satisfies σ(p^a) = (p^(a+1) − 1)/(p − 1) for a prime power (geometric series). So σ(n) = Π (pᵢ^(aᵢ+1) − 1)/(pᵢ − 1). Example: σ(60) = σ(2²) · σ(3) · σ(5) = 7 · 4 · 6 = 168.

How is Euler's totient φ(n) computed? Euler's totient φ(n) is the count of integers in {1, ..., n} coprime to n. It satisfies φ(p^a) = p^(a−1)(p − 1) for a prime power, giving the compact formula φ(n) = n · Π (1 − 1/p) over distinct primes p. Example: φ(60) = 60 · (1/2)(2/3)(4/5) = 16. φ(p) = p − 1 for any prime p, the basis of Fermat's little theorem.

What inputs are supported? Any positive integer from 1 up to about 10²⁵ (twenty-five digits). Inputs ≤ 16 digits use the fast Number path; inputs of 17 to 25 digits use the JavaScript BigInt primitive to keep precision exact. Decimal inputs are rejected; this is an integer-only tool. Negatives are not supported, prime factorisation is conventionally defined on the positive integers.

Why is the trial-division trace sometimes very long? For a number with a small largest prime factor (e.g., 2³⁰) the trial division makes very few attempts because the loop terminates as soon as d > √n. For a number that has only a few prime factors (e.g., 9973 × 99991), the trace goes all the way to the larger of √(p₁ · p₂) or p₂ itself, with thousands of "does not divide" rows in between. The calculator caps the displayed trace at 200 rows and notes when it has been truncated.

Is 1 prime? No. 1 is the multiplicative identity, not a prime. By the standard definition (and Hardy & Wright §1), a prime is a positive integer > 1 whose only positive divisors are 1 and itself. The calculator correctly classifies 1 as a "unit" with empty prime factor list, τ(1) = 1, σ(1) = 1, φ(1) = 1.

What does τ(n) tell us? τ(n) is the count of positive divisors of n. It is multiplicative across coprime factors and equals the product of (aᵢ + 1) across the prime-power factorisation. τ(n) appears in lattice-point counting problems (the number of integer lattice points on a divisor lattice), in the divisor function (Dirichlet series ζ(s)² = Σ τ(n)/n^s), and in the classification of perfect numbers (n is perfect when σ(n) = 2n; the first few perfect numbers correspond to Mersenne primes, giving τ(2^(p−1)(2^p − 1)) = 2p for Mersenne prime p).

What does σ(n) tell us? σ(n) is the sum of all positive divisors of n, including 1 and n itself. It is multiplicative across coprime factors. A perfect number satisfies σ(n) = 2n; an amicable pair is two distinct m, n with σ(m) = σ(n) = m + n; an abundant number has σ(n) > 2n; a deficient number has σ(n) < 2n. The infinite family of even perfect numbers (Euclid-Euler theorem) is given by n = 2^(p−1)(2^p − 1) for Mersenne prime p, and σ(n) = 2n exactly.

What does φ(n) tell us? φ(n) (Euler's totient) is the count of integers ≤ n coprime to n. It governs the multiplicative structure of ℤ/nℤ: the units form a group of order φ(n), Fermat's little theorem is m^(p−1) ≡ 1 (mod p), and the RSA correctness theorem m^(e·d) ≡ m (mod n) requires gcd(e, φ(n)) = 1. φ(p^a) = p^(a−1)(p − 1); φ(pq) = (p − 1)(q − 1) for distinct primes p, q. The φ values are exactly the values of σ(k)/k averaged over divisors k of n, by an identity of Gauss: Σ_{d|n} φ(d) = n.

What's the difference between factorise and factor? "FACTOR-ise" (British) and "factor" (American) both mean the same thing: write n as a product of primes. The calculator uses "factorise" in the button label for clarity but accepts any positive integer input either way. The output is the same in both spellings.

How big can n be? Practically, inputs up to about 10²⁵ (25 digits) work in seconds. Beyond that the trial-division cost scales as √n and the BigInt arithmetic becomes slow. There is no enforced hard limit, try larger inputs if you have patience, but expect the run to take minutes rather than seconds.

Can this handle very large primes like 10¹⁸ + 9? Yes, but it has to trial-divide up to √(10¹⁸ + 9) ≈ 10⁹, which is ~50 million division attempts. That's fast enough on a desktop but not instantaneous. For "is it prime?" questions specifically, dedicated primality tests (Miller-Rabin, AKS) are dramatically faster than trial division. The calculator's "prime" verdict is always correct because the algorithm tests every d ≤ √n, it's just slow for huge n.

**Q:**Can the Prime Factor Calculator be used for professional or commercial purposes?A: Yes, the Prime Factor Calculator provides mathematically correct results that are suitable for professional, commercial, and educational use. For the Prime Factor Calculator, For the Prime Factor Calculator, For high-stakes applications (medical, legal, financial), verify results with a domain expert. For the Prime Factor Calculator, the Prime Factor Calculator formulas used are well-established and validated against reference standards.

**Q:**For the Prime Factor Calculator, How often are the underlying formulas updated?A: the Prime Factor Calculator formulas are based on established scientific, mathematical, or industry-standard references and rarely require updates. When standards change (e.g., new physical constants, revised tax brackets, updated standards), the Prime Factor Calculator is updated to reflect the current authoritative source. For the Prime Factor Calculator, For the Prime Factor Calculator, Each calculator's references section lists the specific sources used.

References

• Hardy, G. H., & Wright, E. M. (2008). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press. §1 (unique factorization), §6 (Euler totient), §16 (multiplicative functions).
• ECMA International. (2020). ECMA-262, ECMAScript 2020 Language Specification, the standard that defines the BigInt primitive used by this calculator for inputs > 2⁵³.
• Rivest, R. L., Shamir, A., & Adleman, L. (1978). "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems." Communications of the ACM, 21(2), 120 to 126., the foundational paper for the RSA cryptosystem, which uses φ(n) as its central constant.
• Lenstra, A. K., & Lenstra, H. W. (1993). The Development of the Number Field Sieve. Springer., modern factoring reference for inputs > 10¹⁰⁰ (well beyond trial division's reach).
• CIPM / BIPM. (2019). SI Brochure (9th ed.). §2.3.1, definition of integer arithmetic and the multiplicative structure of ℕ.
• Caldwell, C. K., & Pomerance, C. (2008). "Primes in the Twentieth Century." In The Princeton Companion to Mathematics., a survey of primality tests and factoring algorithms.