The greatest common divisor of two integers can be defined as the product of their common prime factors, as follows:

$$\displaystyle \begin{align*} A &= p_1^{a_1} \times p_2^{a_2} \times \dots \times p_n^{a_n} \\ B &= p_1^{b_1} \times p_2^{b_2} \times \dots \times p_n^{b_n} \\ \gcd(A, B) &= p_1^{\min(a_1, b_1)} \times p_2^{\min(a_2, b_2)} \times \dots \times p_n^{\min(a_n, b_n)} \end{align*}$$

where ~p_1, \dots, p_n~ are the prime factors and ~a_1, \dots, a_n~, ~b_1, \dots, b_n~ are corresponding exponents.

We can get the factorization of large numbers ~A~ and ~B~ by factorizing every of their given factors and summing the prime number exponents over some prime in all factorizations. The next step is computing the GCD using the expression given above.

An alternative solution would be to find GCD of all pairs of numbers ~A_i, B_j~ and it to the result (multiply), and divide the numbers ~A_i, B_j~ with the same number to prevent adding it to the result several times (in the next iterations).