Prime Factorization Calculator

Find the prime factorization of any number up to 10,000,000 with a visual factor tree. Also calculates GCD and LCM of two numbers with full working shown.

A prime factorization calculator finds the prime factors of an integer, computes the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of two numbers, and determines whether a number is prime. These operations are fundamental in number theory and have practical applications in cryptography, fraction simplification, scheduling, and gear ratio design. Probability & Combinations Calculator and Number Base Converter provide related tools.

Enter the integer to factorise — the calculator finds all prime factors.
For GCD: enter two integers; the result is the largest number dividing both evenly.
For LCM: enter two integers; the result is the smallest number divisible by both.
LCM(a,b) = (a × b) ÷ GCD(a,b) — the calculator uses this relationship.

Prime factorization formulas

GCD(a,b) using Euclidean algorithm: GCD(a,b) = GCD(b, a mod b), repeat until remainder = 0.

LCM(a,b) = (a × b) ÷ GCD(a,b)

Example: GCD(48, 18). 48 = 2×18+12 → GCD(18,12). 18 = 1×12+6 → GCD(12,6). 12 = 2×6+0. GCD = 6. LCM = (48×18)÷6 = 144.

Reading factorization results

Applications

Prime factorization is unique for every integer (Fundamental Theorem of Arithmetic). GCD is used to simplify fractions to lowest terms and find common denominators. LCM is used to find when repeating events coincide (e.g. two gear sizes, recurring scheduling) and to add fractions with different denominators. RSA encryption relies on the difficulty of factorising large semiprimes (products of two large primes).

Math tips and best practices

A number is prime if it has exactly two factors: 1 and itself. 1 is not prime.
To test primality, only check divisors up to √n — if none divide evenly, n is prime.
The GCD of any number and 0 is the number itself: GCD(n, 0) = n.

The largest known prime (as of 2024) has over 41 million digits — found using the GIMPS distributed computing project.
RSA-2048 encryption uses a 2048-bit semiprime (product of two ~300-digit primes) — factorising it would take longer than the age of the universe with current technology.

Common mistakes to avoid

Confusing GCD and LCM — GCD is the largest common factor (used to simplify); LCM is the smallest common multiple (used to find common denominators).
Thinking 1 is prime — by definition, prime numbers have exactly two distinct divisors; 1 has only one (itself).

Number theory calculations are exact for integer inputs within the calculator's numeric range. Very large integers may exceed JavaScript's safe integer limit (2⁵³−1 = 9,007,199,254,740,991) — for very large factorizations, arbitrary-precision libraries should be used. This calculator is for educational purposes.

Frequently Asked Questions

What is prime factorization?

Prime factorization is expressing a number as a product of its prime factors. For example, 60 = 2² × 3 × 5.

What is the difference between GCD and LCM?

GCD (Greatest Common Divisor) is the largest number that divides both numbers exactly. LCM (Least Common Multiple) is the smallest number that is a multiple of both. GCD × LCM = product of the two numbers.

What is the Euclidean algorithm?

The Euclidean algorithm finds the GCD by repeatedly replacing the larger number with the remainder of dividing the two numbers, until the remainder is 0.

How do I find the LCM of two numbers?

LCM(a, b) = (a × b) / GCD(a, b). Alternatively, use prime factorization and take the highest power of each prime factor.

Is 1 a prime number?

No — by definition, a prime number has exactly two distinct divisors: 1 and itself. The number 1 has only one divisor, so it is not prime.