Skip to content

Instantly share code, notes, and snippets.

@endolith
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
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...
@vloddos
Copy link

vloddos commented May 19, 2019

I think there should be floordiv instead of truediv in your lcm

@SmilingBytes
Copy link

SmilingBytes commented Jul 21, 2019

import math

def lcm(a, b):
    return int(a * b / math.gcd(a, b))
print(lcm(2, 6))

@yegane-AI
Copy link

Great code! Can you plz explain me how does GCD works in your program?

@VisionOra
Copy link

Use this line of code to take LCM. Its fast and give you LCM of multiple numbers

import numpy as np
divisor_list = [3,4,5,6,7,2]
int(np.lcm.reduce(divisor_list))

@yegane-AI
Copy link

Use this line of code to take LCM. Its fast and give you LCM of multiple numbers

import numpy as np
divisor_list = [3,4,5,6,7,2]
int(np.lcm.reduce(divisor_list))

Thanks alot

@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