Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
377 views
in Technique[技术] by (71.8m points)

python - Efficiently check if two numbers are co-primes (relatively primes)?

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

For the moment I have this 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

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

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

The only suggestion for improvement might be with your function gcd. Namely, you could use gcd that's defined in math (for Python 3.5) for a speed boost.

Defining coprime2 that uses the built-in version of gcd:

from math import gcd as bltin_gcd

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

You almost cut down execution speed by half due to the fact that math.gcd is implemented in C (see math_gcd in 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

For Python <= 3.4 you could use fractions.gcd but, as noted in a comment by @user2357112, it is not implemented in C. Actually, there's really no incentive to actually use it, its implementation is exactly the same as yours.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...