Quel est le meilleur moyen de vérifier si deux chiffres sont des premiers entre eux?

Question

La première consiste à calculer leur GCD et vérifier si elle est 1.

Y at-il une façon plus rapide?

Answer 1

L'algorithme d'Euclide (calcule gcd) est très rapide. Lorsque deux numéros sont tirés uniformément au hasard à partir [1, n], le nombre moyen d'étapes pour calculer leur gcd est O(log n). Le temps de calcul moyen requis pour chaque étape est quadratique du nombre de chiffres.

Il existe des alternatives qui effectuent un peu mieux (à savoir, chaque étape est subquadratic dans le nombre de chiffres), mais ils ne sont efficaces que sur les très grands entiers. Voir, par exemple, Sur l'algorithme de Schönhage et entier subquadratic GCD calcul .

Answer 2

si vous utilisez sur une machine pour laquelle la division / reste est beaucoup plus cher que les changements, tenez compte binaire GCD .