Efficient check if two numbers are co-primes (relatively primes)?
<p>What is the most efficient ("pythonic") way to test/check if two numbers are <strong>co-primes</strong> (relatively prime) in <strong>Python</strong>.</p>

<p>For the moment I have this code:</p>

<pre><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
</code></pre>

<p>Can the code for checking/testing if two numbers are relatively prime be considered "Pythonic" or there is some better way?</p>

<p>The only suggestion for improvement might be with your function <code>gcd</code>. Namely, you could use <a href="https://docs.python.org/3/library/math.html#math.gcd" rel="nofollow"><code>gcd</code></a> that's defined in <code>math</code> (for Python <code>3.5</code>) for a speed boost.</p>

<p>Defining <code>coprime2</code> that uses the built-in version of <code>gcd</code>:</p>

<pre><code>from math import gcd as bltin_gcd

def coprime2(a, b):
    return bltin_gcd(a, b) == 1
</code></pre>

<p>You almost cut down execution speed by half due to the fact that <code>math.gcd</code> is implemented in <code>C</code> (<a href="https://github.com/python/cpython/blob/master/Modules/mathmodule.c#L688" rel="nofollow">see <code>math_gcd</code> in <code>mathmodule.c</code></a>):</p>

<pre><code>%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
</code></pre>

<p>For Python <code>&lt;= 3.4</code> you could use <code>fractions.gcd</code> but, as noted in a comment by @user2357112, it is not implemented in <code>C</code>. Actually, <em>there's really no incentive to actually use it, <a href="https://hg.python.org/cpython/file/3.4/Lib/fractions.py#l17" rel="nofollow">its implementation is exactly the same as yours.</em></a></p>

python algorithm python-3.x primes relative