Efficace de vérifier si deux nombres sont co-premiers (relativement premiers)?

Ce qui est le plus efficace ("pythonic") de façon à tester/vérifier si deux nombres sont co-nombres premiers (premier) dans Python.

Pour le moment j'ai ce code:

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def coprime(a, b):
    return gcd(a, b) == 1

print(coprime(14,15)) #Should be true
print(coprime(14,28)) #Should be false

Peuvent le code pour vérifier/tester si deux nombres sont premiers entre être considéré comme "Pythonic" ou il ya une meilleure façon?

Semble assez bon.
vous pouvez utiliser math.gcd bien sûr, qui est une batterie incluse et doit être plus performant.
Remarque: math.gcd est nouveau dans Python3.5, a été fractions.gcd avant.
Si c'est code de travail que vous pensez pourrait être amélioré, voir la Revue de Code.

OriginalL'auteur Erba Aitbayev | 2016-09-24

  1. 11

    La seule suggestion d'amélioration pourrait être avec votre fonction gcd. À savoir, vous pouvez utiliser pgcd qui est défini dans math (pour Python 3.5) pour un boost de vitesse.

    Définition coprime2 qui utilise la version intégrée de gcd:

    from math import gcd as bltin_gcd

def coprime2(a, b):
    return bltin_gcd(a, b) == 1

    Vous presque coupé la vitesse d'exécution de moitié en raison du fait que math.gcd est mis en œuvre dans C (reportez-vous à math_gcd mathmodule.c):

    %timeit coprime(14, 15)
1000000 loops, best of 3: 907 ns per loop

%timeit coprime2(14, 15)
1000000 loops, best of 3: 486 ns per loop

    Pour Python <= 3.4 vous pouvez utiliser fractions.gcd mais, comme indiqué dans un commentaire de @user2357112, il n'est pas mis en œuvre dans C. En fait, il n'y a vraiment aucun intérêt à l'utiliser effectivement, sa mise en œuvre est exactement la même que la vôtre.

    Il n'y a pas presque autant de prestations de pré-3.5, bien que, depuis fractions.gcd a été écrit en Python à la place de C.

    OriginalL'auteur Jim Fasarakis Hilliard