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.
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.
Prime factorization is expressing a number as a product of its prime factors. For example, 60 = 2² × 3 × 5.
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.
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.
LCM(a, b) = (a × b) / GCD(a, b). Alternatively, use prime factorization and take the highest power of each prime factor.
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.