Given two numbers. The task is to find the GCD of the two numbers.
Using STL :
In Python, the math module contains a number of mathematical operations, which can be performed with ease using the module. math.gcd() function compute the greatest common divisor of 2 numbers mentioned in its arguments.
Syntax: math.gcd(x, y)
Parameter:
x : Non-negative integer whose gcd has to be computed.
y : Non-negative integer whose gcd has to be computed.
Returns: An absolute/positive integer value after calculating the GCD of given parameters x and y.
Exceptions: When Both x and y are 0, function returns 0, If any number is a character, Type error is raised.
print("The gcd of 60 and 48 is : ", end="") |
Output The gcd of 60 and 48 is : 12
Using Recursion :
print("The gcd of 60 and 48 is : ", end="") |
Output The gcd of 60 and 48 is : 12
Using Euclidean Algorithm :
The Euclid’s algorithm (or Euclidean Algorithm) is a method for efficiently finding the greatest common divisor (GCD) of two numbers. The GCD of two integers X and Y is the largest number that divides both of X and Y (without leaving a remainder).
Pseudo Code of the Algorithm-
- Let a, b be the two numbers
- a mod b = R
- Let a = b and b = R
- Repeat Steps 2 and 3 until a mod b is greater than 0
- GCD = b
- Finish
print('GCD of', a, 'and', b, 'is', gcd(a, b)) |
Output GCD of 98 and 56 is 14
Article Tags :
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 216Note: 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.
Write a Python program to compute the greatest common divisor (GCD) of two positive integers. The greatest common divisor (GCD) of two nonzero integers a and b is the greatest positive integer d such that d is a divisor of both a and b; that is, there are integers e and f such that a = de and b = df, and d is the largest such integer. The GCD of a and b is generally denoted gcd(a, b). Pictorial Presentation: Sample Solution-1: Python Code: Sample Output: Flowchart: The following tool visualize what the computer is doing step-by-step as it executes the said program: Sample Solution-2: Python Code: Sample Output: Flowchart: The following tool visualize what the computer is doing step-by-step as it executes the said program:
Visualize Python code execution:
Visualize Python code execution:
Sample Solution-3:
Use functools.reduce() and math.gcd() over the given list.
Python Code:
from functools import reduce from math import gcd as _gcd def gcd(nums): return reduce(_gcd, nums) nums = [336, 360] print("GCD of",','.join(str(e) for e in nums)) print(gcd(nums)) nums = [12, 17] print("GCD of",','.join(str(e) for e in nums)) print(gcd(nums)) nums = [4, 6] print("GCD of",','.join(str(e) for e in nums)) print(gcd(nums)) nums = [24, 30, 36] print("GCD of",','.join(str(e) for e in nums)) print(gcd(nums))Sample Output:
GCD of 336,360 24 GCD of 12,17 1 GCD of 4,6 2 GCD of 24,30,36 6Flowchart:
Visualize Python code execution:
The following tool visualize what the computer is doing step-by-step as it executes the said program:
Python Code Editor:
Have another way to solve this solution? Contribute your code (and comments) through Disqus.
Previous: Write a Python program that will accept the base and height of a triangle and compute the area.
Next: Write a Python program to get the least common multiple (LCM) of two positive integers.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
Slice a Sequence:
>>> a = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20] >>> # Using a range, [start, end) >>> a[1:3] [2, 4] >>> # Using a range with a step >>> a[1:9:2] [2, 6, 10, 14] >>> # Leave out the start = an implicit start of 0 >>> a[:5] [0, 2, 4, 6, 8] >>> # Leave out the stop = an implicit end to the very last item >>> a[9:] [18, 20] >>> # Entire list >>> a[:] [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
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.