##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
The connection
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.
