LCM and GCD 3 Number - Python

Question

This is my code so far.

from math import gcd

#3 digit lcm calculation
h=input("(1) 2 Digit LCM Or \n(2) 3 Digit LCM\n :")
if h == "2":
    while True:
        def lcm(x, y, z):
            a = gcd(x, y, z)
            num = x
            num2 = y * z // a
            LCM = num * num2 // a

            return LCM

        x = int(input("Number 1: "))
        y = int(input("Number 2: "))
        z = int(input("Number 3: "))
        print("The LCM Of " + str(x) + " And " + str(y) + " And " + str(z) +         " Is " + str(lcm(x, y, z)))

if h == "1":
    while True:
        def lcm(x, y):
            a = gcd(x, y)
            num = x
            num2 = y
            LCM = num * num2 // a

            return LCM
        x = int(input("Number 1: "))
        y = int(input("Number 2: "))
        print("The LCM Of " + str(x) + " And " + str(y) + " Is " + str(lcm(x, y)))

My problem is that the 3 digit just finds a common multiple not the lowest such a 10 , 5 , 8 makes 400 instead of a possible 40. Any help would be useful!

New Code Thanks To Prune

from math import gcd

#3 digit lcm calculation
h=input("(1) 2 Digit LCM Or \n(2) 3 Digit LCM\n :")
if h == "2":
    while True:
        def lcm(x, y, z):
            gcd2 = gcd(y, z)
            gcd3 = gcd(x, gcd2)

            lcm2 = y*z // gcd2
            lcm3 = x*lcm2 // gcd(x, lcm2)
            return lcm3

        x = int(input("Number 1: "))
        y = int(input("Number 2: "))
        z = int(input("Number 3: "))
        print("The LCM Of " + str(x) + " And " + str(y) + " And " + str(z) + " Is " + str(lcm(x, y, z)))

One other thing, Is there another way to mark code instead of having to add 4 spaces in before each and every line. Thanks

This is not your actual code, or you're failing to mention your errors. `math.gcd` only takes two arguments, so `a = gcd(x, y, z)` would die with a `TypeError`. In any event, you're overcomplicating matters. Just write a two number LCM function, and [you can use it to implement an `n` number LCM function trivially](http://stackoverflow.com/q/147515/364696). — ShadowRanger, Feb 28 '17 at 19:45

Prune · Accepted Answer · 2017-02-28T20:08:15.970

ANALYSIS

As you have just discovered (but not yet realized), the relation that holds for pairs of integers:

x * y = GCD(x, y) * LCM(x, y)

does not hold for triples. The basic logic for prime factorization is that the GCD takes the minimum exponent for each prime factor; the LCD takes the maximum exponent. With only two integers, this means that each exponent gets used exactly once, allowing the above equation to hold.

However, with three integers, you guarantee that the middle exponent for each prime factor will be excluded from both the LCM and GCD computations.

 10 = 2^1 * 3^0 * 5^1
  8 = 2^3 * 3^0 * 5^0
  5 = 2^0 * 3^0 * 5^1
----------------------
GCD = 2^0 * 3^0 * 5^0
LCM = 2^3 * 3^0 * 5^1

Note the excluded factors: 2^1 * 3^0 * 5^1 = 10, which is why your LCM computation is high by a factor of 10.

SOLUTION

You need to split the logic when you employ the third integer, something like this:

# Find the 2-number and 3-number GCDs
gcd2 = gcd(y, z)
gcd3 = gcd(x, gcd2)

# Find the 2-number and 3-number LCMs
lcm2 = y*z // gcd2
lcm3 = x*lcm2 // gcd(x, lcm2)

return lcm3

JavDomGom · Answer 2 · 2020-01-08T18:18:21.847

To calculate the GCD of more than two numbers you can do it as follows:

For example: GCD of a, b, c, d

gcd(a, b) = x
gcd(x, c) = y
gcd(y, d) = z

And to calculate the LCM of more than two numbers you can do it as follows:

For example: LCM of a, b, c, d

a * b // gcd(a, b) = x
x * c // gcd(x, c) = y
y * d // gcd(y, d) = z

*Double-slash operator (//) for "floor" division (rounds down to nearest whole number).

GCD in Python 3:

So first we could do it with the following simple while iteration and using gcd() function from math module as follows:

from math import gcd

def gcd_n(*args):
    i = 1
    x = args[0]

    while i < len(args):
        x = gcd(x, args[i])
        i += 1
    return x

It can also be made a little simpler with a lambda function and using reduce() function from functools module as follows:

from math import gcd
from functools import reduce

def gcd_n(*args):
    f = lambda a,b:gcd(a,b)
    return reduce(lambda x,y:f(x,y),args)

But when you think it can't be made easier ... YES, it can be made even easier:

from math import gcd
from functools import reduce

def gcd_n(*args):
    return reduce(gcd, args)

Either way the return is the same. With this simple functions you can calculate the GCD of all the numbers you want, no matter if they are 2, 3, 4 or N numbers.

>>> gcd_n(3355, 985)
5
>>> gcd_n(3465, 6615, 7875)
315
>>> gcd_n(6930, 13230, 15760)
10
>>> gcd_n(1750, 1960, 3080)
70
>>> gcd_n(85, 96, 100, 225)
1

LCM in Python 3:

Following the same philosophy of the simplest example above, to calculate the LCM of two or more numbers, these two functions would suffice:

from math import gcd
from functools import reduce

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

def lcm_n(*args):
    return reduce(lcm, args)

Here you have a sample test series:

>>> lcm_n(77, 9)
693
>>> lcm_n(5, 10, 15)
30
>>> lcm_n(62, 89, 13)
71734
>>> lcm_n(21, 4, 17, 2)
1428

I hope it helps, it works well for me.

LCM and GCD 3 Number - Python

2 Answers2

GCD in Python 3:

LCM in Python 3: