Least Common Multiple (LCM) - Python

Question

This is not much about how do i do it and more about whats wrong with this method. I managed to solve this using other methods but i dont know why i cant with this one. what am i missing here?

Example input: 4,6 Expected output: 12 Actual output: 4

n1, n2 = map(int, input("n1 and n2: ").split(','))

def lcmCalc (n1,n2):
    i = 2
    lcm = 1
    while (n1 != 1) and (n2 != 1):
        if n1 % i == 0 and n2 % i == 0:
            lcm *= i
            n1 = n1/i
            n2 = n2/i
        elif n1 % i != 0 and n2 % i == 0:
            lcm *= i
            n2 = n2/i
        elif n1 % i == 0 and n2 % i != 0:
            lcm *= i
            n1 = n1/i
        else:
            i += 1
    return lcm

print(lcmCalc(n1,n2))

From Python 3 you need to use `//` for int (floor) division. Otherwise you get a float. — khelwood, Jun 18 '20 at 08:49
It doesn't matter in this case, since i am only dividing stuff that % == 0 — AleGPZ, Jun 18 '20 at 08:54
Well, just in case i added // to all divisions. Still getting the same wrong LCM as previously. — AleGPZ, Jun 18 '20 at 08:58
You should include that information in your question: example input, expected output, actual output. — khelwood, Jun 18 '20 at 08:58

score 1 · Accepted Answer · answered Jun 18 '20 at 09:04

You were close. Here are the edits:

def lcmCalc(n1, n2):
    i = 2
    lcm = 1
    while (n1 != 1) and (n2 != 1):
        if n1 % i == 0 and n2 % i == 0:
            lcm *= i
            n1 = n1 // i   # <== use floor division operator
            n2 = n2 // i
        elif n2 % i == 0:  # <== remove unneeded 2nd test
            lcm *= i
            n2 = n2 // i
        elif n1 % i == 0:  # <== remove unneeded 2nd test
            lcm *= i
            n1 = n1 // i
        else:
            i += 1
    return lcm * n1 * n2    # <== need to include residuals

When the outer loop terminates, either of n1 or n2 may still be above 1. That residual needs to be included in the result.

Perhaps you want to include why is the `//` relevant https://stackoverflow.com/questions/588004/is-floating-point-math-broken — norok2, Jun 18 '20 at 09:19

Tony Suffolk 66 · Answer 2 · 2020-06-21T14:18:31.327

I would be tempted to use the relationship :

lcm(a,b) = |a.b| / gcd(a,b)

And of course gcd(a,b) = gcd(b, a%b) & gcd(a,0) = a

So my code :

def gcd(a,b):
    if b ==0:
       return a
    else:
       return gcd(b, a % b)

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

or - if you don't object to a little bit of help from the standard library:

 from math import gcd

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

score 0 · Answer 3 · answered Sep 09 '22 at 13:40

0

def lcm(num1,num2):
    for x in range(1,max(num1,num2)):
        if (num1 % x) == 0 and (num2 % x) == 0:
            e=x
    lcm = (num1 * num2) / e
    return lcm

answered Sep 09 '22 at 13:40

Job Ko

1

Or you could just loop though to find the gcd of the two numbers and then divide the product of the two numbers by the gcd – Job Ko Sep 09 '22 at 13:41

Least Common Multiple (LCM) - Python

3 Answers3