terican

Last verified · v1.0

Calculator · math

Prime Factorization Calculator

Decompose any positive integer into its prime factors instantly. Displays factored form, expanded factor list, and exponent notation.

FreeInstantNo signupOpen source

Inputs

Prime Factorization Result

—

Explain my result

0/3 free

Get a plain-English breakdown of your result with practical next steps.

Prime Factorization Result—

The formula

How the
result is
computed.

What Is Prime Factorization?

Prime factorization is the process of decomposing any positive integer greater than 1 into a unique product of prime numbers. A prime number is any integer greater than 1 with no positive divisors other than 1 and itself — familiar examples include 2, 3, 5, 7, 11, and 13. The Fundamental Theorem of Arithmetic guarantees that every integer n > 1 has exactly one such representation up to the order of factors, making prime factorization a cornerstone of number theory, cryptography, and computational mathematics.

The Prime Factorization Formula

Every positive integer n > 1 can be expressed as:

n = p1a1 × p2a2 × … × pkak

Where:

  • p1 < p2 < … < pk are distinct prime numbers listed in strictly ascending order
  • a1, a2, …, ak are positive integer exponents representing the multiplicity of each prime in the factorization
  • n is the original positive integer being decomposed

As a concrete illustration, 360 = 23 × 32 × 51, because 8 × 9 × 5 = 360. Here k = 3, with p1 = 2 carrying exponent 3, p2 = 3 carrying exponent 2, and p3 = 5 carrying exponent 1.

How to Find Prime Factors: Trial Division

The trial division algorithm is the most transparent method for computing prime factorizations:

  1. Begin with the smallest prime, 2. Divide n by 2 repeatedly until the quotient is no longer evenly divisible; the number of successful divisions is the exponent of 2.
  2. Advance to the next prime (3) and repeat the same repeated-division process.
  3. Continue through successive primes. Only primes p ≤ √n need testing, because any prime factor exceeding √n would force n itself to be prime.
  4. If a remainder greater than 1 remains after testing all primes up to √n, that remainder is itself a prime factor with exponent 1.

Worked example — factorizing 180: Divide by 2 twice (22), leaving 45. Divide 45 by 3 twice (32), leaving 5. Since 5 is prime, the final result is 180 = 22 × 32 × 5.

Key Variables Explained

Number to Factorize

Enter any positive integer greater than 1. Prime inputs such as 97 return a single factor (971). Highly composite numbers such as 720,720 yield many factors: 24 × 32 × 5 × 7 × 11 × 13. A useful derived quantity is the total divisor count: (a1+1)(a2+1)…(ak+1). For 360, this equals (3+1)(2+1)(1+1) = 24 total positive divisors.

Output Type

Three output modes are available: standard factored form presents the compact exponential product (e.g., 23 × 32 × 5); expanded factor list shows each prime repeated according to its multiplicity (e.g., 2, 2, 2, 3, 3, 5); and exponent notation presents the formula variables explicitly. GCF and LCM calculations benefit most from the expanded list, while cryptographic and algebraic applications favor exponent notation.

Real-World Applications

  • Greatest Common Factor (GCF): Multiply shared prime factors at their lowest exponents across both numbers. For GCF(48, 180): 48 = 24 × 3 and 180 = 22 × 32 × 5, so GCF = 22 × 3 = 12.
  • Least Common Multiple (LCM): Multiply all prime factors at their highest exponents. LCM(48, 180) = 24 × 32 × 5 = 720.
  • Fraction Simplification: Dividing numerator and denominator by their GCF, derived from their prime factorizations, reduces any fraction to lowest terms in a single step.
  • RSA Cryptography: RSA encryption security depends on the computational infeasibility of factoring the product of two large primes. A standard 2048-bit RSA key is the product of two primes each roughly 617 digits long — beyond the reach of any current factorization algorithm.
  • Euler's Totient Function: The function φ(n), central to modular arithmetic and public-key cryptography, is computed directly and efficiently from the prime factorization of n using the formula φ(n) = n × ∏(1 − 1/pi).

Methodology and Sources

The trial division algorithm implemented here follows the theoretical framework established in Topics in Number Theory (ScholarWorks@GVSU), which provides a rigorous proof of the Fundamental Theorem of Arithmetic and its computational consequences. Practical verification methodology and symbolic computation examples are drawn from the SDSU Sage as a Calculator Tutorial by Michael O'Sullivan, which demonstrates integer factorization using the Sage mathematical software system. Together these authoritative academic sources ground the calculator in both proven theory and validated implementation practice.

Reference

Frequently asked questions

What is prime factorization and why does it matter in mathematics?
Prime factorization expresses any integer greater than 1 as a unique product of prime numbers — for example, 60 = 2^2 x 3 x 5. It matters because it underpins essential arithmetic operations including computing the greatest common factor and least common multiple of two numbers, reducing fractions to lowest terms, solving Diophantine equations, and securing RSA encryption systems, which rely on the extreme difficulty of factoring large integers into their prime components.
How do you find the prime factorization of a number step by step?
Divide the number repeatedly by the smallest applicable prime starting with 2, then move to 3, 5, 7, and onward, recording each prime and how many times it divides evenly. Continue until the quotient reaches 1. For example, factorizing 84: 84 / 2 = 42, 42 / 2 = 21, 21 / 3 = 7, and 7 is prime. The complete factorization is 84 = 2^2 x 3 x 7. Only primes up to the square root of the number need testing.
What is the prime factorization of 360?
The prime factorization of 360 is 2^3 x 3^2 x 5, because 8 x 9 x 5 = 360. To derive it: divide 360 by 2 three times to obtain 45, divide 45 by 3 twice to obtain 5, and since 5 is prime the process ends. This factorization also reveals that 360 has exactly (3+1)(2+1)(1+1) = 24 positive divisors, making it one of the most divisible three-digit numbers.
How does prime factorization help calculate the GCF and LCM of two numbers?
To find the GCF, identify the prime factors shared by both numbers and multiply them at their lowest matching exponents. To find the LCM, take every prime factor that appears in either number and multiply them at their highest exponents. For example, given 72 = 2^3 x 3^2 and 180 = 2^2 x 3^2 x 5: GCF = 2^2 x 3^2 = 36, and LCM = 2^3 x 3^2 x 5 = 360. Both values follow directly from the factorizations.
Can every positive integer be expressed as a prime factorization?
Yes. The Fundamental Theorem of Arithmetic guarantees that every positive integer greater than 1 has a unique prime factorization, up to the order of the factors. This theorem is one of the most important results in classical number theory. The integer 1 is a special case defined as having an empty prime factorization — no prime factors — which is the convention that preserves uniqueness and consistency across all arithmetic involving prime decompositions.
What is the difference between prime factorization of integers and factoring polynomials?
Prime factorization applies to positive integers and breaks them into irreducible prime number factors — for instance, 30 = 2 x 3 x 5. Polynomial factoring applies to algebraic expressions and decomposes them into lower-degree polynomial factors over a given number field — for example, x^2 - 5x + 6 = (x - 2)(x - 3). Both find irreducible building blocks of a mathematical object, but they operate in entirely different algebraic domains and rely on distinct algorithms and theoretical foundations.