CALTRX

Prime Factorization Calculator

Find the prime factorization of any positive integer. Breaks down numbers into their prime components step by step.

Enter your values above to see the results.

Tips & Notes

  • ✓Use the step-by-step breakdown to understand the solution method, not just to get the answer.
  • ✓Try working the problem by hand first, then use the calculator to verify--this builds mathematical intuition.
  • ✓Pay attention to the order of operations in complex expressions. Parentheses, exponents, multiplication, division, addition, subtraction (PEMDAS).
  • ✓When the result seems unexpected, double-check your input values for typos or unit mismatches.
  • ✓For decimal results, consider whether the context requires rounding and to how many significant figures.

Common Mistakes

  • ✗Stopping factorization at composite factors. 360=4×90 is incomplete — must reach all primes.
  • ✗Missing a prime factor by dividing incorrectly. Always verify: 2³×3²×5=8×9×5=360 ✓.
  • ✗Testing composite divisors unnecessarily. Only primes (2,3,5,7,11...) needed as divisors.
  • ✗GCF error: taking maximum instead of minimum exponents — that gives LCM not GCF.
  • ✗LCM error: only using shared primes. LCM must include ALL primes from both factorizations.

Prime Factorization Calculator Overview

Prime factorization expresses any composite integer as a product of prime numbers — the irreducible building blocks of arithmetic. The Fundamental Theorem of Arithmetic guarantees that this factorization is unique for every integer greater than 1: regardless of which method you use or in which order you find the factors, the final set of prime factors with their exponents is always exactly the same.

The division method works by dividing by the smallest available prime at each step until the quotient reaches 1:

EX: 360 → ÷2=180 → ÷2=90 → ÷2=45 → ÷3=15 → ÷3=5 → 5 is prime → 360 = 2³ × 3² × 5
EX: 504 → ÷2=252 → ÷2=126 → ÷2=63 → ÷3=21 → ÷3=7 → 7 is prime → 504 = 2³ × 3² × 7
Only test prime divisors (2, 3, 5, 7, 11, 13...) and only up to √n — if no prime up to √n divides evenly, the number itself is prime. Once you have the prime factorization, GCF and LCM follow directly from comparing the exponents:
EX: GCF(360, 504) → shared primes: 2³ and 3² → GCF = 8 × 9 = 72
EX: LCM(360, 504) → all primes at max exponent: 2³×3²×5×7 = 8×9×5×7 = 2,520
The number of divisors of any integer can be computed instantly from its prime factorization without listing them individually:
For n = pᵃ × qᵇ × rᶜ: total divisors = (a+1)(b+1)(c+1)
EX: 504 = 2³×3²×7¹ → divisors = (3+1)(2+1)(1+1) = 4×3×2 = 24 divisors
Every integer greater than 1 has a unique prime factorization — this is the Fundamental Theorem of Arithmetic, and it underlies most of number theory. The factorization reveals divisibility completely: n is divisible by m if and only if every prime in m's factorization appears in n's factorization with at least the same exponent. GCF takes minimum exponents across shared primes; LCM takes maximum exponents across all primes. Prime factorization also simplifies root operations: √180 → 180 = 2²×3²×5 → extract paired primes → 2×3×√5 = 6√5. Fraction reduction follows the same logic — divide numerator and denominator by their GCF, which you find by comparing prime factorizations. In cryptography, the difficulty of factoring large numbers into primes is the mathematical foundation of RSA encryption, which secures most online communication.

Frequently Asked Questions

Prime factorization expresses a number as a product of prime numbers only. Method — trial division: divide by 2 repeatedly until odd, then try 3, 5, 7, 11... up to √n. Example: 360. Divide by 2: 360→180→90→45 (three 2s). Divide by 3: 45→15→5 (two 3s). 5 is prime. Result: 360 = 2³ × 3² × 5. Verify: 8 × 9 × 5 = 360 ✓. You only need to test primes up to √360 ≈ 18.97, so test 2, 3, 5, 7, 11, 13, 17.

The Fundamental Theorem of Arithmetic states every integer greater than 1 has a unique prime factorization (ignoring the order of factors). 360 = 2³×3²×5 and only that combination of primes — no other set of primes multiplies to 360. This uniqueness is the foundation of number theory. It guarantees that GCF and LCM calculations are unambiguous, that fraction simplification always reaches a single lowest form, and that RSA encryption keys are unforgeable.

GCF: take shared primes with minimum exponents. LCM: take all primes with maximum exponents. GCF(360, 252): 360 = 2³×3²×5, 252 = 2²×3²×7. Shared primes: 2^min(3,2)=2², 3^min(2,2)=3². GCF = 4×9 = 36. LCM: 2^max(3,2)=2³, 3^max(2,2)=3², 5¹, 7¹. LCM = 8×9×5×7 = 2520. Verify: GCF×LCM = 36×2520 = 90720 = 360×252 ✓. The product relationship GCF(a,b) × LCM(a,b) = a×b always holds for two numbers.

RSA encryption generates a public key by multiplying two large primes p and q to get n = p×q. The security relies on the fact that factoring n back into p and q is computationally infeasible when p and q are each hundreds of digits long. The best known classical algorithm (General Number Field Sieve) takes sub-exponential time but is still impractical for 2048-bit numbers. A quantum computer running Shor's algorithm could factor n in polynomial time — which is why post-quantum cryptography research is urgent.

The count of divisors of n = product of (exponent+1) for each prime factor. 360 = 2³×3²×5¹ → divisors = (3+1)(2+1)(1+1) = 4×3×2 = 24 divisors. The sum of divisors σ(n) = product of (p^(e+1)−1)/(p−1) for each prime factor. σ(360) = (2⁴−1)/(2−1) × (3³−1)/(3−1) × (5²−1)/(5−1) = 15 × 13 × 6 = 1170. A number is perfect if σ(n) = 2n. Euler's totient φ(n) = n × product of (1−1/p) for each distinct prime p.

For large numbers, trial division up to √n is too slow. Better algorithms: Pollard's rho algorithm works in O(n^(1/4)) time and is efficient for numbers up to about 10²⁰. The Quadratic Sieve works for numbers up to about 10¹⁰⁰. The General Number Field Sieve handles numbers beyond 10¹⁰⁰. For everyday use: a number less than 10¹² can be factored in under a second with trial division. A 50-digit number might take milliseconds with Pollard's rho. A 300-digit RSA key is computationally infeasible to factor with current classical computers.