Prime Factorization Calculator
Solve prime factorization problems step-by-step with our free calculator. See formulas, worked examples, and clear explanations.
Calculator
Adjust values & calculateFactorization Steps
Prime Factor Breakdown
All 24 Divisors
GCD and LCM with Common Numbers
Formula
Every integer greater than 1 can be uniquely expressed as a product of prime numbers raised to positive integer exponents. Trial division tests each prime up to sqrt(n), dividing repeatedly. The number of divisors equals the product of (exponent + 1) for each prime factor.
Last reviewed: December 2025
Worked Examples
Example 1: Prime Factorization of 360
Example 2: Comparing Two Numbers via Factorization
Background & Theory
The Prime Factorization Calculator applies the following established principles and formulas. Mathematics rests on a hierarchy of number systems, each extending the previous. The natural numbers (1, 2, 3, ...) support counting and ordering. The integers add negative values and zero, enabling subtraction without restriction. The rational numbers, expressible as p/q where p and q are integers and q is nonzero, close the system under division. The real numbers fill the gaps left by irrationals such as the square root of 2 or pi, forming a complete ordered field. The complex numbers, written as a + bi where i is the square root of negative one, complete the algebraic closure of the reals and allow every polynomial to have a root. Prime factorization states that every integer greater than one is uniquely expressible as a product of primes, a result known as the Fundamental Theorem of Arithmetic. Computing the greatest common divisor (GCD) of two integers relies most efficiently on the Euclidean algorithm: repeatedly replace the larger number with the remainder when it is divided by the smaller, until the remainder is zero. The last nonzero remainder is the GCD. The least common multiple (LCM) follows from the identity LCM(a, b) = |a * b| / GCD(a, b). Modular arithmetic defines equivalence classes of integers that share the same remainder under division by a modulus n. Fermat's Little Theorem and Euler's Theorem arise from this structure and underpin modern cryptography. Logarithms are the inverses of exponential functions. If b raised to the power x equals y, then the logarithm base b of y equals x. The natural logarithm uses base e, approximately 2.71828. Combinatorics counts arrangements and selections. The number of ordered arrangements (permutations) of r objects from n distinct objects is nPr = n! / (n - r)!. The number of unordered selections (combinations) is nCr = n! / (r! * (n - r)!). Pascal's triangle arranges these binomial coefficients so that each entry equals the sum of the two entries directly above it. The Fibonacci sequence, defined by F(1) = 1, F(2) = 1, and F(n) = F(n-1) + F(n-2), appears throughout nature and connects deeply to the golden ratio via Binet's formula.
History
The history behind the Prime Factorization Calculator traces back through the following developments. Mathematics as a systematic discipline traces to ancient Mesopotamia. Babylonian clay tablets dating to around 1800 BCE demonstrate knowledge of quadratic equations, Pythagorean triples, and base-60 arithmetic, suggesting a practical mathematical tradition far preceding Greek formalism. Euclid of Alexandria compiled the Elements around 300 BCE, establishing the axiomatic method that would define rigorous mathematics for over two thousand years. His work organized plane geometry, number theory, and proportion into logically chained propositions derived from a small set of postulates. The algorithm bearing his name for computing GCDs appears in Book VII and remains in use today. In the 9th century, the Persian scholar Muhammad ibn Musa Al-Khwarizmi wrote Al-Kitab al-mukhtasar fi hisab al-jabr wal-muqabala, the treatise whose title gave algebra its name. He systematized the solution of linear and quadratic equations and described procedures that operated on unknowns as objects, a conceptual leap away from purely numerical calculation. Rene Descartes introduced coordinate geometry in 1637 by uniting algebra and Euclidean geometry, allowing curves to be studied through equations. This synthesis set the stage for calculus. Isaac Newton and Gottfried Wilhelm Leibniz independently developed calculus during the 1660s and 1670s, triggering a priority dispute that lasted decades and divided British and Continental mathematicians. Carl Friedrich Gauss proved the Fundamental Theorem of Algebra in 1799, showing that every nonconstant polynomial has at least one complex root. His Disquisitiones Arithmeticae of 1801 established modern number theory. David Hilbert's formalist program at the turn of the 20th century sought to place all of mathematics on an explicit axiomatic foundation, a project that Kurt Godel's incompleteness theorems of 1931 showed to be fundamentally limited. Alan Turing's work in the 1930s on computability introduced the theoretical model of the stored-program computer and linked mathematical logic directly to the limits of algorithmic calculation. His proof that no algorithm can decide in general whether an arbitrary program will halt or run forever placed fundamental boundaries on what mathematics can mechanically determine, and it opened the discipline now known as theoretical computer science.
Key Features
- Solves linear, quadratic, and higher-degree polynomial equations step by step, returning all real and complex roots with full working shown.
- Simplifies fractions to lowest terms and computes ratios and proportions, including cross-multiplication checks and equivalent fraction generation.
- Performs complete prime factorization of any integer and computes the Greatest Common Divisor and Least Common Multiple for sets of numbers.
- Handles matrix operations including addition, scalar multiplication, matrix multiplication, determinant calculation, and full matrix inversion for square matrices.
- Evaluates all standard trigonometric functions and their inverses in degrees or radians, and verifies common trigonometric identities symbolically.
- Calculates permutations, combinations, and binomial coefficients for combinatorics problems, supporting both formula display and step-by-step breakdown.
- Converts integers between binary, octal, decimal, and hexadecimal bases instantly, with optional display of the positional value expansion.
- Computes the sum of arithmetic and geometric sequences given the first term, common difference or ratio, and number of terms, with formula derivation.
Frequently Asked Questions
Formula
n = p1^a1 * p2^a2 * ... * pk^ak (Fundamental Theorem of Arithmetic)
Every integer greater than 1 can be uniquely expressed as a product of prime numbers raised to positive integer exponents. Trial division tests each prime up to sqrt(n), dividing repeatedly. The number of divisors equals the product of (exponent + 1) for each prime factor.
Worked Examples
Example 1: Prime Factorization of 360
Problem: Find the complete prime factorization of 360 and determine the number of divisors.
Solution: 360 / 2 = 180\n180 / 2 = 90\n90 / 2 = 45\n45 / 3 = 15\n15 / 3 = 5\n5 / 5 = 1\n\n360 = 2^3 * 3^2 * 5^1\n\nNumber of divisors = (3+1)(2+1)(1+1) = 4*3*2 = 24\nSum of divisors = (1+2+4+8)(1+3+9)(1+5) = 15*13*6 = 1170
Result: 360 = 2^3 * 3^2 * 5 | 24 divisors | Sum = 1170 | phi(360) = 96
Example 2: Comparing Two Numbers via Factorization
Problem: Find the GCD and LCM of 252 and 198 using prime factorization.
Solution: 252 = 2^2 * 3^2 * 7\n198 = 2 * 3^2 * 11\n\nGCD: Take minimum exponents of shared primes\nGCD = 2^min(2,1) * 3^min(2,2) = 2^1 * 3^2 = 2 * 9 = 18\n\nLCM: Take maximum exponents of all primes\nLCM = 2^2 * 3^2 * 7 * 11 = 4 * 9 * 7 * 11 = 2772\n\nVerification: GCD * LCM = 18 * 2772 = 49896 = 252 * 198
Result: GCD(252, 198) = 18 | LCM(252, 198) = 2772
Frequently Asked Questions
What is prime factorization and why is it unique?
Prime factorization is the process of expressing a composite number as a product of prime numbers. The Fundamental Theorem of Arithmetic guarantees that every integer greater than 1 has a unique prime factorization, aside from the order of the factors. For example, 360 = 2^3 * 3^2 * 5, and there is no other set of primes whose product is 360. This uniqueness is not trivial to prove and was rigorously established by Euclid and later refined by Gauss. The theorem serves as the cornerstone of number theory and has profound implications for mathematics. It ensures that prime numbers are truly the building blocks of all integers, analogous to atoms in chemistry. Without unique factorization, many fundamental theorems in algebra and number theory would fail.
How does the trial division method work for finding prime factors?
Trial division is the simplest and most intuitive algorithm for prime factorization. Start by dividing the number by the smallest prime, 2, and continue dividing by 2 as long as the result is even. Then try 3, then 5, and continue with each successive prime. For each prime, divide repeatedly until it no longer divides evenly, counting the number of times it divides (this count becomes the exponent). A crucial optimization is that you only need to test primes up to the square root of the remaining quotient, because if the quotient has no factor less than or equal to its square root, it must itself be prime. For example, factoring 84: 84/2=42, 42/2=21, 21/3=7, and 7 is prime. So 84 = 2^2 * 3 * 7. While trial division is slow for very large numbers, it works well for numbers up to about 10^12.
What is the relationship between prime factorization and finding divisors?
Prime factorization provides a complete recipe for generating all divisors of a number. If n = p1^a1 * p2^a2 * ... * pk^ak, then every divisor of n has the form p1^b1 * p2^b2 * ... * pk^bk where 0 <= bi <= ai for each i. The total number of divisors equals (a1+1)(a2+1)...(ak+1). For 360 = 2^3 * 3^2 * 5^1, the number of divisors is (3+1)(2+1)(1+1) = 4*3*2 = 24. The sum of divisors formula uses geometric series for each prime power: sigma(n) = (p1^(a1+1)-1)/(p1-1) * (p2^(a2+1)-1)/(p2-1) * ... This multiplicative structure arises because divisors of n correspond to choosing an exponent for each prime factor independently. These formulas are much faster than checking every number up to n for divisibility.
How is Euler totient function calculated from prime factorization?
Euler totient function phi(n) counts integers from 1 to n that are coprime to n (share no common prime factors with n). Using the prime factorization n = p1^a1 * p2^a2 * ... * pk^ak, the formula is phi(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk). Equivalently, phi(n) = p1^(a1-1)*(p1-1) * p2^(a2-1)*(p2-1) * ... For example, phi(360) = phi(2^3 * 3^2 * 5) = 2^2*(2-1) * 3^1*(3-1) * 5^0*(5-1) = 4*1*3*2*1*4 = 96. The totient function is multiplicative, meaning phi(a*b) = phi(a)*phi(b) when gcd(a,b) = 1. This function is central to RSA cryptography, where it determines the private key, and appears in many areas of number theory including Euler theorem: a^phi(n) is congruent to 1 modulo n for coprime a and n.
Why is prime factorization important in cryptography?
The security of RSA encryption, the most widely used public-key cryptosystem, rests entirely on the difficulty of factoring large numbers. RSA uses a public modulus n that is the product of two large primes p and q, each typically 1024 bits or larger. While multiplying p and q to get n takes microseconds, factoring n back into p and q is computationally infeasible with current technology and algorithms. The best-known factoring algorithm, the General Number Field Sieve, has sub-exponential but super-polynomial running time. In 2020, a 829-bit number was factored as a research milestone, requiring enormous computational resources. RSA-2048 (a 2048-bit modulus) is expected to remain secure for decades. If efficient factoring algorithms were discovered, or if large-scale quantum computers implementing Shor algorithm become practical, RSA would be broken, which motivates ongoing research into post-quantum cryptography.
How do you compute GCD and LCM using prime factorization?
Prime factorization provides elegant formulas for the greatest common divisor (GCD) and least common multiple (LCM) of two numbers. For the GCD, take the minimum exponent of each shared prime factor. For the LCM, take the maximum exponent of each prime factor appearing in either number. For example, with 360 = 2^3*3^2*5 and 84 = 2^2*3*7: GCD takes min exponents of shared primes: 2^min(3,2) * 3^min(2,1) = 2^2*3 = 12. LCM takes max exponents of all primes: 2^max(3,2) * 3^max(2,1) * 5^max(1,0) * 7^max(0,1) = 2^3*3^2*5*7 = 2520. The fundamental identity GCD(a,b) * LCM(a,b) = a*b always holds. While the Euclidean algorithm computes GCD more efficiently without factoring, the factorization approach gives deeper insight into the relationship and naturally extends to computing GCD and LCM of more than two numbers.
References
Reviewed by Manoj Kumar, Mathematics Educator · Editorial policy