Compute the greatest common divisor and least common multiple of two integer
- Details
- Category: 11th Class computer practicals
- Published: Friday, 11 June 2021 05:55
- Written by Super User
- Hits: 362
number1=int(input('enter the first number'))
number2=int(input('enter the second number'))
gcd=0
remainder=-1
if(number1>number2):
dividend=number1
divisor=number2
while(remainder!=0):
remainder=dividend%divisor
dividend=divisor
gcd=divisor
divisor=remainder
lcm=int(number2/gcd)*number1
print('gcd is '+str(gcd)+' LCM is '+str(lcm))
else:
dividend=number2
divisor=number1
while(remainder!=0):
remainder=dividend%divisor
dividend=divisor
gcd=divisor
divisor=remainder
lcm=int(number1/gcd)*number2
print('gcd is '+str(gcd)+' LCM is '+str(lcm))
Explanation : GCD means greatest common divisor , it means we have to find the highest common factor of 2 numbers. LCM means least common multiple. It means we have to find lowest common factor for 2 numbers.
In this program we are taking smaller number as divisor and bigger as dividend as usual, in mathematics. So we will go on dividing the number untill we get remainder as zero. The process of HCF is followed here at each step. At each step divisor is used as dividend and remainder is becoming divisor the quotient value is assigned to GCD variable at each loop.
So finally GCD will contain value of divisor which completely divides number and remainder is zero. To find the LCM we used the formula and printed the GCD and LCM of the 2 numbers. Program is divided in simple if, else conditional Structure, execution will flow according to condition.