Skip to content

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
 # 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...

### 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)```

### kovalevcon commented Jan 14, 2019 • edited Loading

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

### SmilingBytes commented Jul 21, 2019 • edited Loading

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

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