Last active
November 4, 2016 21:25
-
-
Save haikentcode/03da844ffbc8d9f9d3e019593babb2e6 to your computer and use it in GitHub Desktop.
find lcm of array ( list ) in python
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
def gcd(a,b): | |
# if a==0: | |
# return b | |
# return gcd(b%a,a) | |
return agcd(a,b) | |
def agcdUtil(a,b,p): | |
if a==0: | |
p[0]=0 | |
p[1]=1 | |
return b | |
ans=agcdUtil(b%a,a,p) | |
x=p[1]-int(b/a)*p[0] | |
y=p[0] | |
p[0]=x | |
p[1]=y | |
return ans | |
def agcd(a,b): | |
point=[0,0] | |
return agcdUtil(a,b,point) | |
def lcm(A): | |
""" | |
#two | |
lcm(a,b) = a*b /gcd(a,b) | |
_______________________________ | |
#list | |
x = A0 | |
lcm(A) = L[1:n-1] {Ai*x/gcd(Ai*x)=>x} | |
# A list , Ai i'th in list ,L loop | |
""" | |
x=A.pop(0) | |
for a in A: | |
x = a*x/gcd(a,x) | |
return x | |
if __name__ == "__main__": | |
a=[2, 7, 3, 9, 4] | |
print lcm(a) #252 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment