Greatest Common Divisor -

gcd_main.py


#!/usr/bin/env python3


from gcd import *


def main():
    G = GCD(16, 88)
    G.gcd()
    print("")
    print(G.gcd_euclid.__doc__)
    G.gcd_euclid()
    H = GCD(16, 88)
    H.gcd_euclid2()


if __name__ == '__main__':
    main()

gcd.py


#!/usr/bin/env/ python3

class GCD:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def gcd(self):
        # find smaller number
        print("")
        smaller_number = 0
        if self.x > self.y:
            smaller_number = self.y
        else:
            smaller_number = self.x

        # use smaller number to calculate greatest common divisor
        GCD = 0
        for i in range(1, smaller_number + 1):
            if (self.x % i == 0) and (self.y % i == 0):
                GCD = i
        print("The Greatest Common divisor of {} and {} is {}".format(self.x, self.y, GCD))

    def gcd_euclid(self):
        ''' DOC: Euclidean method: Number m can be written as m = qn + r, where q in the quotient and
        r is the reminder. Recursive substitution of r with q and q with m until the remainder is 0
        will ultimately deliver the GCD for the pair since gcd(n,0) = n.
        '''
        a = self.x
        b = self.y
        r_val = self.x % self.y
        q_val = int(self.x / self.y)
        while r_val != 0:
            self.x = self.y
            self.y = r_val
            q_val = int(self.x / self.y)
            r_val = self.x - (self.y * q_val)
        print("The Greatest Common divisor of {} and {} using euclidean method is {}".format(a, b, self.y))

    def gcd_euclid2(self):
        a = self.x
        b = self.y
        if self.x < self.y:
            (self.x, self.y) = (self.y, self.x)
        while self.x % self.y != 0:
            (self.x, self.y) = (self.y, self.x % self.y)

        print("The Greatest Common divisor of {} and {} using euclidean method two is {}".format(a, b, self.y))

output.py


The Greatest Common divisor of 16 and 88 is 8

 DOC: Euclidean method: Number m can be written as m = qn + r, where q in the quotient and
        r is the reminder. Recursive substitution of r with q and q with m until the remainder is 0
        will ultimately deliver the GCD for the pair since gcd(n,0) = n.
        
The Greatest Common divisor of 16 and 88 using euclidean method is 8
The Greatest Common divisor of 16 and 88 using euclidean method two is 8

Process finished with exit code 0