Qual é a maneira mais rápida para verificar se dois números dados são primos entre si?

Question

Uma maneira é calcular a sua gcd e verificar se ele é 1.

Existe alguma maneira mais rápida?

Answer 1

O algoritmo de Euclides (calcula gcd) é muito rápido. Quando dois números são desenhados de modo uniforme de forma aleatória a partir de [1, n], o número médio de passos para calcular a sua gcd é O(log n). O tempo médio de computação necessário para cada passo é quadrática no número de dígitos.

Existem alternativas que realizam um pouco melhor (isto é, cada passo é subquadratic no número de dígitos), mas eles só são eficazes em grandes números inteiros. Veja, por exemplo, algoritmo do On Schönhage e subquadratic inteiro gcd computação .

Answer 2

Se você está rodando em uma máquina para a qual divisão / restante é significativamente mais caro do que mudanças, considere binário GCD .