pythonfunctionproceduregreatest-common-divisor

Brief and Dynamical Algorithm for GCD(A, B, C) - in Python. Function for Greatest Common Divisor of 3 random integers


def GCD3(A, B, C):
    if A == B == 0://
        return C
    if A == C == 0:
        return B
    if B == C == 0://
        return A
    if B == 0:
        B = A
        A = 0
    elif C == 0:
        C = A
        A = 0
    gcd1 = A
    gcd2 = A
    while True:
        r = gcd1 % B
        gcd1 //= B
        gcd1 = B
        B = r
        if B == 0:
            while True:
                r = gcd2 % C
                gcd2 //= C
                gcd2 = C
                C = r
                if C == 0:
                    while True:
                        r = gcd1 % gcd2
                        gcd1 //= gcd2
                        gcd1 = gcd2
                        gcd2 = r
                        if gcd2 == 0:
                            return abs(gcd1)


print(GCD3(2, 0, 0))
print(GCD3(115, 5, 0))
print(GCD3(49, 27, 31))
print(GCD3(56, 12, 48))
print(GCD3(8, 56, 4))

Is there any way to make this code dynamical and brief. Simply, how can I make this code smaller? The first 3 if statements are for the cases when two of the numbers are 0. Next if, elif statements are for putting in order if one of the numbers are zero, looking like this: gcd(0, a, b) no matter which is zero it puts in this order by assigning. When I checked gcd(a, b, c)=gcd[gcd(a,b), gcd(a,c)]. Nested while loops are for checking gcd(gcd1, gcd2). Again, is there any way to make this code dynamical and brief. Simply, how can I make this code smaller?


Solution

  • Not efficient, but here's one way:

    import math
    
    
    def factors(item):
        ret = set()
        for i in range(1, math.ceil(item/2)+1):
            if not item % i:
                ret.add(i)
        ret.add(item)
        return ret
    
    
    def gcdx(*args):
        return max(set.intersection(*[factors(i) for i in args]))
    
    print(gcdx(6,12,24))
    

    Yields

    6