Skip to content

Instantly share code, notes, and snippets.

Last active June 22, 2022 23:33
Show Gist options
  • Save endolith/114336 to your computer and use it in GitHub Desktop.
Save endolith/114336 to your computer and use it in GitHub Desktop.
GCD and LCM functions in Python for several numbers
# Greatest common divisor of 1 or more numbers.
from functools import reduce
def gcd(*numbers):
Return the greatest common divisor of 1 or more integers
>>> gcd(5)
>>> gcd(30, 40)
>>> gcd(120, 40, 60)
# Am I terrible for doing it this way?
from math import gcd
return reduce(gcd, numbers)
# Least common multiple is not in standard libraries? It's in gmpy, but this
# is simple enough:
def lcm(*numbers):
Return lowest common multiple of 1 or more integers.
>>> lcm(5)
>>> lcm(30, 40)
>>> lcm(120, 40, 60)
def lcm(a, b):
return (a * b) // gcd(a, b)
return reduce(lcm, numbers, 1)
# Assuming numbers are positive integers...
Copy link

It's not mentioned here, but this is the Euclidean algorithm for computing the GCD:

Love how short the code is!

Copy link

def find_gcd(a,b):
gcd = 1
for i in range(1,a+1):
if a%i==0 and b%i==0:
gcd = i
return gcd

first = int(input('Enter first number: '))
second = int(input('Enter second number: '))

print('HCD of %d and %d is %d' %(first, second, find_gcd(first, second)))

lcm = first * second / find_gcd(first, second)
print('MCM of %d and %d is %d' %(first, second, lcm))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment