Skip to content

Instantly share code, notes, and snippets.

@endolith
Last active June 22, 2022 23:33
  • Star 75 You must be signed in to star a gist
  • Fork 11 You must be signed in to fork a gist
Star You must be signed in to star a gist
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
Examples
--------
>>> gcd(5)
5
>>> gcd(30, 40)
10
>>> gcd(120, 40, 60)
20
"""
# 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.
Examples
--------
>>> lcm(5)
5
>>> lcm(30, 40)
120
>>> lcm(120, 40, 60)
120
"""
def lcm(a, b):
return (a * b) // gcd(a, b)
return reduce(lcm, numbers, 1)
# Assuming numbers are positive integers...
@astrojuanlu
Copy link

It's not mentioned here, but this is the Euclidean algorithm for computing the GCD: https://en.wikipedia.org/wiki/Euclidean_algorithm

Love how short the code is!

@naemazam
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))
print("azam")

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