View Discussion
Improve Article
Save Article
View Discussion
Improve Article
Save Article
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.
Python3
import math
print["The gcd of 60 and 48 is : ", end=""]
print[math.gcd[60, 48]]
Output
The gcd of 60 and 48 is : 12
Using Recursion :
Python3
def hcf[a, b]:
if[b == 0]:
return a
else:
return hcf[b, a % b]
a = 60
b = 48
print["The gcd of 60 and 48 is : ", end=""]
print[hcf[60, 48]]
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
Python3
def gcd[a, b]:
if [a == 0]:
return b
if [b == 0]:
return a
if [a == b]:
return a
if [a > b]:
return gcd[a-b, b]
return
gcd[a, b-a]
a = 98
b = 56
if[gcd[a, b]]:
print['GCD of', a, 'and', b, 'is', gcd[a, b]]
else:
print['not found']
Output
GCD of 98 and 56 is 14
View Discussion
Improve Article
Save Article
View Discussion
Improve Article
Save Article
Given two integer x and y, the task is to find the HCF of the numbers without using recursion or Euclidean method.
Examples:
Input: x = 16, y = 32
Output: 16Input: x = 12, y = 15
Output: 3
Approach: HCF of two numbers is the greatest number which can divide both the numbers. If the smaller of the two numbers can divide the larger number then the HCF is the smaller number. Else starting from [smaller / 2] to 1 check whether the current element divides both the numbers . If yes, then it is the required HCF.
Below is the implementation of the above approach:
C++
#include
using namespace std;
int getHCF[int x, int y]
{
int minimum = min[x, y];
if [x % minimum == 0 && y % minimum == 0]
return minimum;
for [int i = minimum / 2; i >= 2; i--] {
if
[x % i == 0 && y % i == 0]
return i;
}
return 1;
}
int main[]
{
int x = 16, y = 32;
cout = 2; i--]
{
if [x % i == 0 && y % i == 0]
return i;
}
return 1;
}
public static void main[String[] args]
{
int x = 16, y = 32;
System.out.println[getHCF[x, y]];
}
}
Python3
def getHCF[x, y]:
minimum = min[x, y]
if [x % minimum == 0 and y % minimum == 0]:
return minimum
for i in range[minimum // 2, 1, -1]:
if [x %
i == 0 and y % i == 0]:
return i
return 1
x, y = 16, 32
print[getHCF[x, y]]
C#
using System;
class GFG
{
static int getHCF[int x, int y]
{
int minimum = Math.Min[x, y];
if [x % minimum == 0 && y % minimum == 0]
return minimum;
for [int i = minimum / 2; i >= 2; i--]
{
if [x % i == 0 && y % i == 0]
return i;
}
return 1;
}
static void Main[]
{
int x = 16, y = 32;
Console.WriteLine[getHCF[x, y]];
}
}
PHP
Javascript
function getHCF[x, y]
{
var minimum = Math.min[x, y];
if [x % minimum == 0 && y % minimum == 0]
return minimum;
for[var i = minimum / 2; i >= 2; i--]
{
if [x % i == 0 && y % i == 0]
return
i;
}
return 1;
}
var x = 16, y = 32;
document.write[getHCF[x, y]];
Time Complexity: O[min[x, y]], here x and y are two input parameters.
Auxiliary Space: O[1], since no extra space has been taken.