# Prime Factorization & Divisors Calculator Decompose a number into its prime factors and get its total divisor count and Euler totient, with clear step-by-step results instantly. --- - **Canonical URL:** https://dothecalculation.com/calculators/prime-factorization-calculator - **Category:** Math calculators - **Publisher:** Do The Calculation (https://dothecalculation.com) - **Cost:** Free, no account or sign-up required - **Privacy:** Runs entirely in the browser; inputs are never sent to a server - **Methodology:** https://dothecalculation.com/methodology --- ## Prime Factorization & Divisors Calculator Decompose an integer into its unique prime factor product, and get its total divisor count and Euler's totient with full step-by-step work. - Fundamental Theorem of Arithmetic prime product formulas - Trial division factorization with full step-by-step work - Divisor count τ(n) & Euler's totient φ(n) for the entered integer ## Prime Factorization Fundamentals: The Fundamental Theorem of Arithmetic Prime factorization is the mathematical decomposition of a composite positive integer into a unique product of prime numbers (integers greater than 1 with no positive divisors other than 1 and themselves). The Fundamental Theorem of Arithmetic states that every integer \(n > 1\) either is a prime number itself or can be represented uniquely as a product of prime powers, up to the order of factors: $$n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k} = \prod_{i=1}^{k} p_i^{e_i}$$ where \(p_1 < p_2 < \dots < p_k\) are distinct prime numbers and \(e_i \ge 1\) are integer exponents. For example, the prime factorization of \(360\) is: $$360 = 2^3 \cdot 3^2 \cdot 5^1 = 8 \cdot 9 \cdot 5$$ No other set of prime numbers can multiply to produce 360. Prime factorization provides the foundational building blocks for number theory, modular arithmetic, algebra, fraction reduction, and modern public-key cryptography (RSA encryption). ## Prime Factorization Algorithms: Trial Division and Beyond The computational difficulty of factoring large integers increases rapidly with number size, making integer factorization a central topic in computational complexity theory. This calculator uses trial division — the simplest and most transparent factorization algorithm. It tests potential prime divisors \(d = 2, 3, 5, 7, 11, \dots\) up to \(\sqrt{n}\); if no prime factor is found below \(\sqrt{n}\), the remaining value is itself prime. Trial division runs in \(O(\sqrt{n})\) time, which is fast and exact for the everyday-sized integers this calculator targets, though impractically slow for the massive (100+ digit) numbers used in cryptography research. For very large numbers, faster probabilistic methods exist — Pollard's Rho algorithm and the General Number Field Sieve (GNFS) are the standard choices in cryptographic research, but they aren't implemented here since this calculator is built for everyday integers, not multi-hundred-digit RSA moduli. ## Beyond This Calculator: GCD and LCM via Prime Factorization This calculator factors one integer at a time — it doesn't take two numbers and compute their GCD or LCM directly. That said, prime factorization is a classic way to find both by hand once you have two factorizations: run this calculator once per number, then combine the exponents. To find the GCD of two integers \(a = \prod p_i^{a_i}\) and \(b = \prod p_i^{b_i}\), take the minimum exponent of each shared prime factor: $$\text{GCD}(a, b) = \prod p_i^{\min(a_i, b_i)}$$ To find the LCM, take the maximum exponent across all prime factors present in either number: $$\text{LCM}(a, b) = \prod p_i^{\max(a_i, b_i)}$$ GCD and LCM satisfy the identity \(\text{GCD}(a, b) \cdot \text{LCM}(a, b) = a \cdot b\). For example, for \(a = 360 = 2^3 \cdot 3^2 \cdot 5^1\) and \(b = 300 = 2^2 \cdot 3^1 \cdot 5^2\): \(\text{GCD}(360, 300) = 2^2 \cdot 3^1 \cdot 5^1 = 60\) and \(\text{LCM}(360, 300) = 2^3 \cdot 3^2 \cdot 5^2 = 1800\) (verification: \(60 \times 1800 = 108{,}000 = 360 \times 300\)). If you just need a GCD or LCM directly, the [Euclidean algorithm calculator](/calculators/euclidean-algorithm-calculator) computes one without requiring a full factorization. ## Euler's Totient Function φ(n) and the Divisor Count Prime factorization enables direct calculation of number-theoretic functions that count divisors and coprime integers — both of which this calculator computes for you automatically. Euler's Totient Function \(\phi(n)\) counts the number of positive integers up to \(n\) that are coprime to \(n\). Using prime factorization, it's calculated via Euler's product formula: $$\phi(n) = p_1^{e_1-1}(p_1 - 1) \cdots p_k^{e_k-1}(p_k - 1)$$ For \(n = 360 = 2^3 \cdot 3^2 \cdot 5^1\): \(\phi(360) = 360 \times \frac{1}{2} \times \frac{2}{3} \times \frac{4}{5} = 96\). The divisor count function \(\tau(n)\) (also written \(d(n)\)) gives the total number of positive divisors of \(n\): $$\tau(n) = \prod_{i=1}^{k} (e_i + 1)$$ For \(360 = 2^3 \cdot 3^2 \cdot 5^1\), \(\tau(360) = (3+1)(2+1)(1+1) = 24\) total divisors. This calculator reports the count directly, though it doesn't list out all 24 divisor values individually. Euler's totient function underlies Euler's Theorem (\(a^{\phi(n)} \equiv 1 \pmod n\)), which is the mathematical basis of RSA key generation. ## RSA Cryptography and the Computational Intractability of Factoring Modern internet security, HTTPS encryption, digital signatures, and secure financial transactions depend directly on the mathematical difficulty of prime factorization. The RSA cryptosystem generates a public key by selecting two massive prime numbers \(p\) and \(q\) (each 1024+ bits long) and computing their product \(N = p \cdot q\). Decrypting a message requires knowing the private key, which depends on \(\phi(N) = (p-1)(q-1)\) — the same totient function this calculator computes for smaller numbers. While multiplying two 1024-bit primes takes a fraction of a millisecond, finding the prime factors of their 2048-bit product using the fastest known classical algorithms would take an impractically long time. This asymmetry — easy multiplication, hard factorization — is the security foundation of RSA. (Quantum computers running Shor's Algorithm could in principle break this asymmetry, which is why post-quantum cryptography standards are being developed.) ## How to Use This Calculator Enter any integer of 2 or greater. The calculator performs trial division, shows each division step, and reports the full prime factorization along with the divisor count \(\tau(n)\) and Euler's totient \(\phi(n)\). ## Worked Example: Factoring 360 (the Calculator's Default) $$360 = 2^3 \cdot 3^2 \cdot 5^1$$ $$\tau(360) = (3+1)(2+1)(1+1) = 24 \text{ divisors}$$ $$\phi(360) = 360 \times \tfrac{1}{2} \times \tfrac{2}{3} \times \tfrac{4}{5} = 96$$ So 360 has 24 total positive divisors, and 96 integers from 1 to 360 share no common factor with it. ## Related Calculators To check whether a single number is prime or generate a list of primes in a range, use the [prime number calculator](/calculators/prime-number-calculator). For GCD, LCM, and Bézout coefficients between two numbers, see the [Euclidean algorithm calculator](/calculators/euclidean-algorithm-calculator). ## Applications in Computer Science and Beyond Beyond cryptography, prime numbers and prime factorization play roles across other fields. In computer science, hash tables often use prime-sized buckets to reduce collision clustering, and the Fast Fourier Transform runs fastest when the sample size is a power of 2 or a product of small primes. In music theory, just-intonation tuning uses small prime frequency ratios (2:1 octave, 3:2 perfect fifth) to build consonant chords. In evolutionary biology, periodical cicadas evolved prime-numbered (13-year and 17-year) life cycles, which is thought to reduce overlap with predator population cycles. ## Frequently asked questions ### What is Prime Factorization? Prime factorization is the unique decomposition of a composite number into a product of prime number factors. ### What is the Fundamental Theorem of Arithmetic? It states that every integer greater than 1 is either a prime number itself or can be represented uniquely as a product of prime powers. ### How do you find the prime factors of a number? Divide the number by the smallest prime factor (2, 3, 5...) repeatedly until the quotient becomes 1, recording each prime factor — this is the trial-division method this calculator uses. ### Does this calculator compute the GCD or LCM of two numbers directly? No — it factors one integer at a time. You can combine two factorizations by hand using the min/max-exponent method described above, or use the dedicated Euclidean algorithm calculator for a direct GCD/LCM. ### Does this calculator list all the divisors of a number? No — it reports the total divisor count τ(n), not the individual divisor values. ### What is Euler's Totient Function φ(n)? It counts the number of positive integers up to n that are coprime to n, calculated directly from the prime factorization — one of this calculator's reported outputs. ### Why is prime factorization important in RSA cryptography? RSA security relies on the asymmetry that multiplying two large primes is fast, but factoring their large product back into prime factors is computationally impractical for classical computers. ### What is Trial Division? Trial division is a factorization method that tests potential prime divisors from 2 up to the square root of the target number. It's what this calculator uses. ### What is Shor's Algorithm? Shor's Algorithm is a quantum computing algorithm capable of factoring large integers in polynomial time, posing a theoretical future threat to RSA encryption. ### Why do hash tables sometimes use prime numbers for their size? Prime table sizes help minimize hash key collisions by making certain patterns in the input data less likely to align with the table's stride, spreading data more evenly. ## Related concepts - **Fundamental Theorem of Arithmetic** — The mathematical theorem stating that every integer > 1 has a unique prime factorization. - **Euler Totient Function** — A number-theoretic function counting integers up to n that are coprime to n. - **RSA Encryption** — A public-key cryptosystem whose security is based on the computational difficulty of prime factorization. ## Related guides - [Fraction Operations Guide: Add, Subtract, Multiply, Divide](https://dothecalculation.com/blog/math/fraction-operations-guide) — Learn the rules for adding, subtracting, multiplying, and dividing fractions, with simplification steps and live DTC calculator workflows. ## Related calculators - [Partial Fractions Decomposition Calculator](https://dothecalculation.com/calculators/partial-fractions-calculator) — Decompose rational expressions with distinct or repeated linear-factor denominators into partial fractions, shown in clear step-by-step form. - [Fourier Series Coefficient Synthesizer](https://dothecalculation.com/calculators/fourier-series-calculator) — Decompose periodic waveforms like square, triangle, and sawtooth into sine and cosine Fourier series coefficients instantly. - [Mixed Number Fraction Calculator](https://dothecalculation.com/calculators/mixed-number-calculator) — Add, subtract, multiply, divide, and simplify mixed number fractions with clear step-by-step conversions and instant results. - [Prime Number Checker & List Generator](https://dothecalculation.com/calculators/prime-number-calculator) — Check primality, find the next prime, and generate prime numbers within a custom range using fast sieve methods instantly. - [Number Base Converter](https://dothecalculation.com/calculators/base-converter) — Convert whole numbers between binary, octal, decimal, and hexadecimal instantly, with positional-notation and successive-division proofs shown. - [Complex Number & Phasor Calculator](https://dothecalculation.com/calculators/complex-number-calculator) — Add, subtract, multiply, divide, and find roots of complex numbers, with automatic rectangular-to-polar phasor conversion, using this free calculator. --- _This mathematical calculator is designed for educational, scientific, and engineering computations. Always verify matrix dimensions, boundary conditions, and floating-point precision limits when applying results to mission-critical engineering or physics systems._ --- _Source: [Do The Calculation](https://dothecalculation.com/calculators/prime-factorization-calculator). Quote freely with attribution and a link to this page._