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

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

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