Primality & Factorization
Status
-
Prime Factorization
-
GCD & LCM Calculator
Greatest Common Divisor (GCD)
0
The largest positive integer that divides both numbers without a remainder.
Least Common Multiple (LCM)
0
The smallest positive integer that is divisible by both numbers.
How it Works
Prime Factorization is finding which prime numbers multiply together to make the original number.
The Fundamental Theorem of Arithmetic states that every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers uniquely (up to the order of the factors).
Algorithm: We use trial division up to the square root of \( n \). This is efficient for most numbers that fit within JavaScript's safe integer limit (\( 2^{53} - 1 \)).
GCD (Greatest Common Divisor): Calculated using the highly efficient Euclidean algorithm: \(\text{gcd}(a, 0) = a\) and \(\text{gcd}(a, b) = \text{gcd}(b, a \pmod b)\).
LCM (Least Common Multiple): Derived directly from GCD using the formula: \(\text{lcm}(a, b) = \frac{|a \times b|}{\text{gcd}(a, b)}\).