How to enhance the time complexity of finding if N is Coprime with the numbers from 2 till N using Python?

Question

I have wrote my code, it consists of 2 methods coprime() to check if 2 numbers are coprime or not and count_coprime() to count the numbers which are comprime with n and it works, yet it is too slow and I am looking for improvements:

1st:

def coprime(a, b):
    # Returns a boolean value
    # Returns true if a and b are in fact coprime
    if a == 1 or b == 1:
        return True
    else:
        count = 0
        if a < b:
            for i in range(2, a + 1):
                if a % i == 0:
                    if b % i == 0:
                        count += 1
        else:
            for i in range(2, b + 1):
                if b % i == 0:
                    if a % i == 0:
                        count += 1
        return count < 1

2nd:

def count_coprimes(n):
    count = 1
    for i in range(2, n):
        if coprime(i, n):
            count += 1
    return count

[Efficiently check if two numbers are co-primes (relatively primes)?](https://stackoverflow.com/a/39679114/1014587) — Mast, Jul 23 '20 at 07:03
thanks for your comment, but what I want know is how `gcd()` was implemented in such efficient way ? what is happening behind the scene ? — Sam AlGhamian, Jul 23 '20 at 16:50

score 2 · Accepted Answer · edited Mar 25 '23 at 01:39

2

To check whether two numbers are coprime, you can use GCD (Great Common Divisor) algorithm. If gcd(a,b)==1, then values are coprime. It works in O(max(log(a),log(b))) time, so overall compexity is O(logn).

There are some proofs for this here.

Note that standard math module already contains math.gcd() function. Simple implementation of Euclid's algorithm:

def EuclideanGCD(x, y): 
    while y: 
        x, y = y, x % y 
    return x

edited Mar 25 '23 at 01:39

cdutra

587
6
15

answered Jul 23 '20 at 07:01

MBo

77,366
5
53
86

thanks for your answer, but what I want know is how `gcd()` was implemented in such efficient way? what is happening behind the scene ? – Sam AlGhamian Jul 23 '20 at 16:49
Knowing "gcd" term, you can easily find and read thousands descriptions and implementations. Added canonic Python implementation. – MBo Jul 23 '20 at 17:12

How to enhance the time complexity of finding if N is Coprime with the numbers from 2 till N using Python?

1 Answers1