Teaching Kids Programming: Videos on Data Structures and Algorithms
Greate Common Divisor Algorithm
GCD aka Greatest Common Disvisor is the largest common divisor of two positive integers. For example, GCD(25, 35) is 5 because both 25 and 35 appears in 5’s time table. We can imagine that 1 is in also one of the common divisor but normally is the smallest.
Two numbers if their GCD is 1, we can call them co-prime. For example, 7 and 6 are co-prime.
We can compute the GCD using the following classic algorithm:
def gcd(a, b):
while b > 0:
a, b = b, a % b
return a
Least Common Multiples
Least Common Multiples aka LCM can be computed via the following: LCM(a, b) = a * b / GCD(a, b). For example, LCM of 15 and 20 is 15*20/GCD(20, 15) = 60 as you can see, 60 is the least common multiple of 15 and 20.
def lcm(a, b):
return a * b / gcd(a, b)
–EOF (The Ultimate Computing & Technology Blog) —
273 wordsLast Post: Depth First Search and Breadth First Search Algorithm to Compute the Left Side View of a Binary Tree
Next Post: Algorithms to Check Narcissistic Number