~x, y~ son coprimos si y solo si ~gcd(x, y) = 1~. Además se cumple ~gcd (a, x) \le gcd (a \cdot b, x)~. Por lo tanto, en lugar de elegir un número entero ~a \cdot b (a, b> 1)~, es mejor elegir ~a~ (Nota: si ~a \cdot b~ es un divisor común, entonces ~a~ también es un divisor común). Ese es, dada una solución óptima ~P~, si un número entero ~a \cdot b (a, b> 1)~ estuviera contenido en los divisores comunes seleccionado en ~P~, entonces puede elegir a en su lugar. Por lo tanto, existe una solución óptima que solo consta de ~1~ y primos. Además, tú puede elegir todos los divisores comunes que sea ~1~ o un primo, por lo que es óptimo elegir todos ellos. Entonces, ¿cómo podemos encontrar tales divisores comunes? Una forma en que la consideración y la implementación son ambos fáciles es factorizar ~A~, ~B~ en factores primos (tomará un total de ~O (\max({\sqrt{A}, \sqrt{B}}))~ tiempo cada uno) y encuentre los factores primos comunes. El número de factores primos es ~O (log A)~, ~O (log B)~ cada uno, para que pueda encontrar los factores primos comunes ingenuamente a tiempo. Es óptimo elegir 1 y factores primos comunes, por lo que la respuesta será el número de factores primos comunes sumados por 1.

Con un poco más de consideración, parece que ~x~ es un divisor común de ~A~ y ~B~ si y solo si ~x~ es un divisor de ~gcd (A, B)~, entonces puedes factorizar ~gcd (A, B)~ en factores primos y contar los número de factores primos. Esto deja un tiempo de ~O (\min({\sqrt{A}, \sqrt{B}}))~