¿Cuál es la manera más rápida para comprobar si son primos entre sí dos números dados?

Question

Una forma es calcular su mcd y comprobar si es 1.

¿Hay alguna forma más rápida?

Answer 1

El algoritmo de Euclides (calcula gcd) es muy rápido. Cuando dos números se dibujan de manera uniforme al azar de [1, n], el número medio de pasos para calcular su gcd es O(log n). El promedio de tiempo de cálculo necesario para cada paso es cuadrática en el número de dígitos.

Hay alternativas que realizan algo mejor (es decir, cada paso es subquadratic en el número de dígitos), pero que sólo son eficaces en números enteros muy grandes. Véase, por ejemplo, En el algoritmo de Schönhage y subquadratic número entero mcd cómputo .

Answer 2

si se está ejecutando en una máquina para la que la división / resto es significativamente más caro que los cambios, considere binaria GCD .