Write a program to compute the greatest common divisor and least common multiple of two integers.

Compute the greatest common divisor and least common multiple of two integers

Table of Contents Show

Objective- Compute the greatest common divisor and least common multiple of two integers using Python.
Source Code :
Explaination of code :
Download of Source Code – click here
Output of LCM and GCD program in python
for more python programs -> click here
Example #1: GCD Using for loop and if Statement
Example #2: GCD Using while loop and if...else Statement
Example #3: GCD for both positive and negative numbers
Program to Compute LCM
Program to Compute LCM Using GCD

# GCD PROGRAM num1 = int(input("Enter 1st number: ")) num2 = int(input("Enter 2nd number: ")) i = 1 while(i <= num1 and i <= num2): if(num1 % i == 0 and num2 % i == 0): gcd = i i = i + 1 print("Greatest Common Divisor (GCD) is ", gcd) # LCM PROGRAM if num1 > num2: greater = num1 else: greater = num2 while(True): if((greater % num1 == 0) and (greater % num2 == 0)): lcm = greater break greater += 1 print("The Least Common Multiple (LCM) is ", lcm)

Output:

Enter 1st number: 3 Enter 2nd number: 5 ('Greatest Common Divisor (GCD) is ', 1) ('The Least Common Multiple (LCM) is ', 15) >>> Enter 1st number: 5 Enter 2nd number: 10 ('Greatest Common Divisor (GCD) is ', 5) ('The Least Common Multiple (LCM) is ', 10) >>>

Compute the greatest common divisor(GCD) and least common multiple( LCM)of two integers. LCM and GCD / HCF program in python. This python project is useful for beginners and CBSE KV School Class 11 and Class 12 students computer science practical file and NIELIT O Level Programming and Problem Solving through Python (Module M3-R5).

Objective- Compute the greatest common divisor and least common multiple of two integers using Python.

Highest Common Factor (HCF): The greatest common factor to any two or more than two integer numbers is known as HCF of those numbers. For example, HCF of 12 and 18 is 6. Also try:

Lowest Common Multiple (LCM): The smallest or lowest common multiple of any two or more than two integer numbers is termed as LCM. For example, LCM of 12 and 18 is 36.

Source Code :

Screenshot of the source code

Explaination of code :

def find_gcd(a,b): #function greatest common deviser taking a,b as input gcd = 1 #Initialization for i in range(1,a+1): #for loop if a%i==0 and b%i==0: # checks for a divisor that divides both of a and b greater value will be come in gcd gcd = i return gcdfirst = int(input(‘Enter first number: ‘)) #entering inputsecond = int(input(‘Enter second number: ‘))print(‘HCF or GCD of %d and %d is %d’ %(first, second, find_gcd(first, second)))lcm = first * second / find_gcd(first, second)

print(‘LCM of %d and %d is %d’ %(first, second, lcm))

Download of Source Code – click here

Output of LCM and GCD program in python

Testing

Numbers are input 15 and 4. we know that HCF is 1 and LCM is 60.Second number inputs are 20 and 15.we know HCF is 5 and LCM Is 60.

Both of the inputs are correct. Hence Testing is done.

Result

The result is positive and objective is achieved.

for more python programs -> click here

Hello World Program in Python

Input a welcome message and display it in Python

Display the larger / smaller number in Python.

Greatest of Three Numbers in Python using Nested if

Patterns using nested loop in Python

Program to Print Pattern in Python

Program to input the value of x and n and sum of series in Python

Python Program for Armstrong, Prefect Number, Palindrome

Program of Prime number by recursion in python

Prime Number Program in Python

Write a Program to Print Fibonacci Series in Python

LCM and GCD program in Python

Python program to count number of vowels in a string

Whether a String is Palindrome or not in Python

Bubble Sort Program in Python

Linear search in python using list

Program to read a text file in python

Python program to read a file line by line

Program to Count Vowels and Consonants in Python

Stack Program in Python

Queue Program in Python

Python Leap Year Program for Beginners

Python Program to Print Series and Addition

Binary Search Program in Python

Program to find sum of digits in python

Sum of numbers divisible by 3 and 5 in python

Thanks for visit at Python Programs for Class 11 and 12 post.

The HCF or GCD of two integers is the largest integer that can exactly divide both numbers (without a remainder).

There are many ways to find the greatest common divisor in C programming.

Example #1: GCD Using for loop and if Statement

#include <stdio.h> int main() { int n1, n2, i, gcd; printf("Enter two integers: "); scanf("%d %d", &n1, &n2); for(i=1; i <= n1 && i <= n2; ++i) { // Checks if i is factor of both integers if(n1%i==0 && n2%i==0) gcd = i; } printf("G.C.D of %d and %d is %d", n1, n2, gcd); return 0; }

In this program, two integers entered by the user are stored in variable n1 and n2.Then, for loop is iterated until i is less than n1 and n2.

In each iteration, if both n1 and n2 are exactly divisible by i, the value of i is assigned to gcd.

When the for loop is completed, the greatest common divisor of two numbers is stored in variable gcd.

Example #2: GCD Using while loop and if...else Statement

#include <stdio.h> int main() { int n1, n2; printf("Enter two positive integers: "); scanf("%d %d",&n1,&n2); while(n1!=n2) { if(n1 > n2) n1 -= n2; else n2 -= n1; } printf("GCD = %d",n1); return 0; }

Output

Enter two positive integers: 81 153 GCD = 9

This is a better way to find the GCD. In this method, smaller integer is subtracted from the larger integer, and the result is assigned to the variable holding larger integer. This process is continued until n1 and n2 are equal.

The above two programs works as intended only if the user enters positive integers. Here's a little modification of the second example to find the GCD for both positive and negative integers.

Example #3: GCD for both positive and negative numbers

#include <stdio.h> int main() { int n1, n2; printf("Enter two integers: "); scanf("%d %d",&n1,&n2); // if user enters negative number, sign of the number is changed to positive n1 = ( n1 > 0) ? n1 : -n1; n2 = ( n2 > 0) ? n2 : -n2; while(n1!=n2) { if(n1 > n2) n1 -= n2; else n2 -= n1; } printf("GCD = %d",n1); return 0; }

Output

Enter two integers: 81 -153 GCD = 9

You can also use recursion to find the GCD.

The least common multiple (L.C.M.) of two numbers is the smallest positive integer that is perfectly divisible by the two given numbers.

For example, the L.C.M. of 12 and 14 is 84.

Program to Compute LCM

# Python Program to find the L.C.M. of two input number def compute_lcm(x, y): # choose the greater number if x > y: greater = x else: greater = y while(True): if((greater % x == 0) and (greater % y == 0)): lcm = greater break greater += 1 return lcm num1 = 54 num2 = 24 print("The L.C.M. is", compute_lcm(num1, num2))

Output

The L.C.M. is 216

Note: To test this program, change the values of num1 and num2.

This program stores two number in num1 and num2 respectively. These numbers are passed to the compute_lcm() function. The function returns the L.C.M of two numbers.

In the function, we first determine the greater of the two numbers since the L.C.M. can only be greater than or equal to the largest number. We then use an infinite while loop to go from that number and beyond.

In each iteration, we check if both the numbers perfectly divide our number. If so, we store the number as L.C.M. and break from the loop. Otherwise, the number is incremented by 1 and the loop continues.

The above program is slower to run. We can make it more efficient by using the fact that the product of two numbers is equal to the product of the least common multiple and greatest common divisor of those two numbers.

Number1 * Number2 = L.C.M. * G.C.D.

Here is a Python program to implement this.

Program to Compute LCM Using GCD

# Python program to find the L.C.M. of two input number # This function computes GCD def compute_gcd(x, y): while(y): x, y = y, x % y return x # This function computes LCM def compute_lcm(x, y): lcm = (x*y)//compute_gcd(x,y) return lcm num1 = 54 num2 = 24 print("The L.C.M. is", compute_lcm(num1, num2))

The output of this program is the same as before. We have two functions compute_gcd() and compute_lcm(). We require G.C.D. of the numbers to calculate its L.C.M.

So, compute_lcm() calls the function compute_gcd() to accomplish this. G.C.D. of two numbers can be calculated efficiently using the Euclidean algorithm.

Click here to learn more about methods to calculate G.C.D in Python.