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

endolith commented Jun 14, 2012

@MaddieKeller
Copy link

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

@gjorgiev
Copy link

gjorgiev commented Mar 3, 2017

good, thanks :)

@qzane
Copy link

qzane commented Mar 29, 2017

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

from functools import reduce

@TheFern2
Copy link

TheFern2 commented Nov 1, 2017

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

@tyler-austin
Copy link

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

Copy link

ghost commented Jan 7, 2018

Thanks for it!!

@AaronConlon
Copy link

thank you!

@Tardis07
Copy link

Excellent! How elegant it is.

@goutham9032
Copy link

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
Copy link

thanks very much for the sharing

@kkimdev
Copy link

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
Copy link

kovalevcon commented Jan 14, 2019

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
Copy link
Author

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

Copy link

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