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:
1 2 3 4 | def gcd(a, b): while b > 0: a, b = b, a % b return a |
def gcd(a, b):
while b > 0:
a, b = b, a % b
return aLeast 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.
1 2 | def lcm(a, b): return a * b / gcd(a, b) |
def lcm(a, b): return a * b / gcd(a, b)
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
290 wordsloading...
Last 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
