Every GCD can be computed from prime factorizations: for each prime p, take the minimum power appearing in a or b.
Example: 120 = 2³ × 3 × 5, 90 = 2 × 3² × 5. gcd = 2¹ × 3¹ × 5¹ = 30.
But factorization is slow for large numbers. Euclidean algorithm is faster because it does not need to factor.