Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
GCD and LCM functions in Python for several numbers
# 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)
@endolith

This comment has been minimized.

@MaddieKeller

This comment has been minimized.

Copy link

@MaddieKeller MaddieKeller commented Jan 6, 2016

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

@gjorgiev

This comment has been minimized.

Copy link

@gjorgiev gjorgiev commented Mar 3, 2017

good, thanks :)

@qzane

This comment has been minimized.

Copy link

@qzane qzane commented Mar 29, 2017

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

from functools import reduce
@TheFern2

This comment has been minimized.

Copy link

@TheFern2 TheFern2 commented Nov 1, 2017

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

@tyler-austin

This comment has been minimized.

Copy link

@tyler-austin tyler-austin commented Dec 6, 2017

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

@ghost

This comment has been minimized.

Copy link

@ghost ghost commented Jan 7, 2018

Thanks for it!!

@youyiqin

This comment has been minimized.

Copy link

@youyiqin youyiqin commented Feb 13, 2018

thank you!

@Tardis07

This comment has been minimized.

Copy link

@Tardis07 Tardis07 commented Mar 11, 2018

Excellent! How elegant it is.

@goutham9032

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

@Ericwonne Ericwonne commented Jul 18, 2018

thanks very much for the sharing

@kkimdev

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link
Owner Author

@endolith endolith commented Jan 14, 2019

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

@ghost

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

@vloddos vloddos commented May 19, 2019

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

@ismail-h-rana

This comment has been minimized.

Copy link

@ismail-h-rana ismail-h-rana commented Jul 21, 2019

import math

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

This comment has been minimized.

Copy link

@yegane-AI yegane-AI commented Jul 23, 2019

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

@SohaibAnwaar

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

@yegane-AI 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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

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

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