Instantly share code, notes, and snippets.

# endolith/gcd_and_lcm.py

Last active June 22, 2022 23:33
Show Gist options
• Save endolith/114336 to your computer and use it in GitHub Desktop.
GCD and LCM functions in Python for several numbers
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 # GCD and LCM are not in math module. They are in gmpy, but these are simple enough: def gcd(a,b): """Compute the greatest common divisor of a and b""" while b > 0: a, b = b, a % b return a def lcm(a, b): """Compute the lowest common multiple of a and b""" return a * b / gcd(a, b)

### MaddieKeller commented Jan 6, 2016

This is the simplest lcm formula I could find. Thanks!

### gjorgiev commented Mar 3, 2017

good, thanks :)

For python3 support, maybe you should add (it's also compatible with python2 )

`from functools import reduce`

### TheFern2 commented Nov 1, 2017

For python3 use
`from math import gcd`
fraction gcd has been deprecated.

### tyler-austin commented Dec 6, 2017

what does *numbers look like? What is the expected parameter?

Thanks for it!!

thank you!

### Tardis07 commented Mar 11, 2018

Excellent! How elegant it is.

### goutham9032 commented Jun 19, 2018

For case of n no's in python 2.7

``````>>> from fractions import gcd
>>> def get_gcd(*nos):
...     return reduce(gcd,nos)
...
>>> get_gcd(120,40,60)
20
>>> get_gcd(30,40)
10

``````

### Ericwonne commented Jul 18, 2018

thanks very much for the sharing

### kkimdev commented Aug 19, 2018

Concatenated everything for the convenience.

```from functools import reduce
from fractions import gcd

def lcm(a, b):
return a * b / gcd(a, b)

def lcms(*numbers):
return reduce(lcm, numbers)

def gcds(*numbers):
return reduce(gcd, numbers)```

Last update for Python 3:

``````from functools import reduce
from math import gcd

def lcm(a, b):
return int(a * b / gcd(a, b))

def lcms(*numbers):
return reduce(lcm, numbers)
``````

### endolith commented Jan 14, 2019

@kovalevcon Why int(float division) instead of int division?

### ghost commented Mar 25, 2019

Easy! Just do:
import math
ans = math.gcd(8, 10)
For lcm, do:
import math
ans = math.lcm(8, 10)
or:
import math
gcd_ans = math.gcd(8, 10)
lcm_ans = 8 * 10 / gcd_ans
I got it from this site:
https://www.geeksforgeeks.org/gcd-in-python/
Check it out!

### vloddos commented May 19, 2019

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

```import math

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

### yegane-AI commented Jul 23, 2019

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

### VisionOra commented Jun 13, 2020

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 commented Jun 13, 2020

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 commented Jun 9, 2021

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 commented Sep 26, 2021

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")