other way to solve Least common multiple of two integers a and b-CodePudding

PPCM which is the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, is the smallest positive integer that is divisible by both a and b. Since division of integers by zero is undefined, this definition has meaning only if a and b are both different from zero. However, some authors define lcm(a,0) as 0 for all a, since 0 is the only common multiple of a and 0.

a=int(input("Valeur de a ?")) 
b=int(input("Valeur de b ?"))
print('les diviseures de a : ')
tab_a = []
tab_b = []
tab_c = []
for i in range(1,a 1):
    if(a%i==0):
        tab_a.append(i)
print(tab_a)
print('les diviseures de b : ')
for j in range(1,b 1):
    if(b%j==0):
        tab_b.append(j)
print(tab_b)
l=0
if(a>b):
        sh = len(tab_b)
        lg = len(tab_a)
        arr_sh = tab_b
        arr_lg = tab_a
else:
        sh = len(tab_a)
        lg = len(tab_b)
        arr_sh = tab_a
        arr_lg = tab_b

for i in range(0,sh):
    for j in range(0,lg):
            if(arr_sh[i]==arr_lg[j]):
                    tab_c.append(arr_sh[i])
print(tab_c)
print('PPCM est :',tab_c[0])

I think my approach is long, how can I improve it?

CodePudding user response：

The lcm is computed from the gcd and the latter using Euclid's agorithm.

def gcd(a, b):
    while b > 0:
        a, b= b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

(The trivial cases are not handled.)

CodePudding user response：

You can do this with a single loop; there's no need to build a bunch of lists and make multiple passes over them or anything like that:

>>> def lcm(a, b):
...     a, b = sorted((a, b))
...     return next(i for i in range(b, a * b   1, b) if i % a == 0)
...
>>> lcm(2, 4)
4
>>> lcm(20, 16)
80

This is O(min(a, b)) in time and O(1) in space.