MCD (máximo común divisor) o HCF (máximo común divisor) de dos números es el número más grande que divide a ambos.
C++
// C++ program to find GCD of two numbers
#include <iostream>
using namespace std;
// Function to return gcd of a and b
int gcd(int a, int b)
{
int result = min(a, b); // Find Minimum of a nd b
while (result > 0) {
if (a % result == 0 && b % result == 0) {
break;
}
result--;
}
return result; // return gcd of a nd b
}
// Driver program to test above function
int main()
{
int a = 98, b = 56;
cout << "GCD of " << a << " and " << b << " is "
<< gcd(a, b);
return 0;
}
// This code is contributed by Suruchi Kumari
C
// C program to find GCD of two numbers
#include <math.h>
#include <stdio.h>
// Function to return gcd of a and b
int gcd(int a, int b)
{
int result = fmin(a, b); // Finding minimum of a nd b
while (result > 0) {
if (a % result == 0 && b % result == 0) {
break;
}
result--;
}
return result; // return gcd of a nd b
}
// Driver program to test above function
int main()
{
int a = 98, b = 56;
printf("GCD of %d and %d is %d ", a, b, gcd(a, b));
return 0;
}
// This code is contributed by Suruchi Kumari
Java
// Java program to find GCD of two numbers
public class GFG {
// Function to return gcd of a and b
static int gcd(int a, int b)
{
int result = Math.min(a, b); // Find Minimum of a nd b
while (result > 0) {
if (a % result == 0 && b % result == 0) {
break;
}
result--;
}
return result; // return gcd of a nd b
}
// Driver program to test above function
public static void main (String[] args)
{
int a = 98, b = 56;
System.out.print("GCD of " + a + " and " + b + " is " + gcd(a, b));
}
}
// This code is contributed by AnkThon
Python3
# Python program to find GCD of two numbers
# Function to find gcd of two numbers
def gcd(a, b):
# Find minimum of a and b
result = min(a, b)
while result:
if a % result == 0 and b % result == 0:
break
result -= 1
# Return the gcd of a and b
return result
# Driver Code
a = 98
b = 56
print(f"GCD of {a} and {b} is {gcd(a, b)}")
# This code is contributed by Soham Mirikar
C#
// C# program to find GCD of two numbers
using System;
public class GFG
{
// Function to return gcd of a and b
static int gcd(int a, int b)
{
int result = Math.Min(a, b); // Find Minimum of a nd b
while (result > 0) {
if (a % result == 0 && b % result == 0) {
break;
}
result--;
}
return result; // return gcd of a nd b
}
// Driver program to test above function
public static void Main (string[] args)
{
int a = 98, b = 56;
Console.WriteLine("GCD of " + a + " and " + b + " is " + gcd(a, b));
}
}
// This code is contributed by AnkThon
Javascript
<script>
// Javascript program to find GCD of two numbers
// Function to return gcd of a and b
function gcd(a,b)
{
let result = Math.min(a, b); // Find Minimum of a nd b
while (result > 0) {
if (a % result == 0 && b % result == 0) {
break;
}
result--;
}
return result; // return gcd of a nd b
}
// Driver program to test above function
let a = 98;
let b = 56;
console.log("GCD of ",a," and ",b," is ",gcd(a, b));
// This code is contributed by akashish__
</script>
C++
// C++ program to find GCD of two numbers
#include <iostream>
using namespace std;
// Recursive function to return gcd of a and b
int gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return gcd(a-b, b);
return gcd(a, b-a);
}
// Driver program to test above function
int main()
{
int a = 98, b = 56;
cout<<"GCD of "<<a<<" and "<<b<<" is "<<gcd(a, b);
return 0;
}
C
// C program to find GCD of two numbers
#include <stdio.h>
// Recursive function to return gcd of a and b
int gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return gcd(a-b, b);
return gcd(a, b-a);
}
// Driver program to test above function
int main()
{
int a = 98, b = 56;
printf("GCD of %d and %d is %d ", a, b, gcd(a, b));
return 0;
}
Java
// Java program to find GCD of two numbers
class Test
{
// Recursive function to return gcd of a and b
static int gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return gcd(a-b, b);
return gcd(a, b-a);
}
// Driver method
public static void main(String[] args)
{
int a = 98, b = 56;
System.out.println("GCD of " + a +" and " + b + " is " + gcd(a, b));
}
}
Python3
# Recursive function to return gcd of a and b
def gcd(a,b):
# Everything divides 0
if (a == 0):
return b
if (b == 0):
return a
# base case
if (a == b):
return a
# a is greater
if (a > b):
return gcd(a-b, b)
return gcd(a, b-a)
# Driver program to test above function
a = 98
b = 56
if(gcd(a, b)):
print('GCD of', a, 'and', b, 'is', gcd(a, b))
else:
print('not found')
# This code is contributed by Danish Raza
C#
// C# program to find GCD of two
// numbers
using System;
class GFG {
// Recursive function to return
// gcd of a and b
static int gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return gcd(a - b, b);
return gcd(a, b - a);
}
// Driver method
public static void Main()
{
int a = 98, b = 56;
Console.WriteLine("GCD of "
+ a +" and " + b + " is "
+ gcd(a, b));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to find GCD
// of two numbers
// Recursive function to
// return gcd of a and b
function gcd($a, $b)
{
// Everything divides 0
if ($a == 0)
return $b;
if ($b == 0)
return $a;
// base case
if($a == $b)
return $a ;
// a is greater
if($a > $b)
return gcd( $a-$b , $b ) ;
return gcd( $a , $b-$a ) ;
}
// Driver code
$a = 98 ;
$b = 56 ;
echo "GCD of $a and $b is ", gcd($a , $b) ;
// This code is contributed by Anivesh Tiwari
?>
Javascript
<script>
// Javascript program to find GCD of two numbers
// Recursive function to return gcd of a and b
function gcd(a, b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return gcd(a-b, b);
return gcd(a, b-a);
}
// Driver program to test above function
let a = 98, b = 56;
document.write("GCD of "+ a + " and " + b + " is " + gcd(a, b));
// This code is contributed by Mayank Tyagi
</script>
C++
// C++ program to find GCD of two numbers
#include <bits/stdc++.h>
using namespace std;
int static dp[1001][1001];
// Function to return gcd of a and b
int gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// if a value is already
// present in dp
if(dp[a][b] != -1)
return dp[a][b];
// a is greater
if (a > b)
dp[a][b] = gcd(a-b, b);
// b is greater
else
dp[a][b] = gcd(a, b-a);
// return dp
return dp[a][b];
}
// Driver program to test above function
int main()
{
int a = 98, b = 56;
memset(dp, -1, sizeof(dp));
cout<<"GCD of "<<a<<" and "<<b<<" is "<<gcd(a, b);
return 0;
}
Java
// Java program to find GCD of two numbers
import java.util.*;
public class GFG
{
static int [][]dp = new int[1001][1001];
// Recursive function to return gcd of a and b
static int gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// if a value is already
// present in dp
if(dp[a][b] != -1)
return dp[a][b];
// a is greater
if (a > b)
dp[a][b] = gcd(a-b, b);
// b is greater
else
dp[a][b] = gcd(a, b-a);
// return dp
return dp[a][b];
}
// Driver method
public static void main(String[] args)
{
for(int i = 0; i < 1001; i++) {
for(int j = 0; j < 1001; j++) {
dp[i][j] = -1;
}
}
int a = 98, b = 56;
System.out.println("GCD of " + a +" and " + b + " is " + gcd(a, b));
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# function to return gcd of a and b
# Taking the matrix as globally
dp = [[-1 for i in range(1001)] for j in range(1001)]
def gcd(a,b):
# Everything divides 0
if (a == 0):
return b
if (b == 0):
return a
# base case
if (a == b):
return a
if(dp[a][b] != -1):
return dp[a][b]
# a is greater
if (a > b):
dp[a][b] = gcd(a-b, b)
else:
dp[a][b] = gcd(a, b-a)
return dp[a][b]
# Driver program to test above function
a = 98
b = 56
if(gcd(a, b)):
print('GCD of', a, 'and', b, 'is', gcd(a, b))
else:
print('not found')
# This code is contributed by Samim Hossain Mondal.
C#
// C# program to find GCD of two numbers
using System;
class GFG
{
static int [,]dp = new int[1001, 1001];
// Recursive function to return gcd of a and b
static int gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// if a value is already
// present in dp
if(dp[a, b] != -1)
return dp[a, b];
// a is greater
if (a > b)
dp[a, b] = gcd(a-b, b);
// b is greater
else
dp[a, b] = gcd(a, b-a);
// return dp
return dp[a, b];
}
// Driver method
public static void Main()
{
for(int i = 0; i < 1001; i++) {
for(int j = 0; j < 1001; j++) {
dp[i, j] = -1;
}
}
int a = 98, b = 56;
Console.Write("GCD of " + a +" and " + b + " is " + gcd(a, b));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
//<script>
// Javascript program to find GCD of two numbers
var dp = new Array(1001);
// Loop to create 2D array using 1D array
for (var i = 0; i < dp.length; i++) {
dp[i] = new Array(1001);
}
// Function to return gcd of a and b
function gcd(a, b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// if a value is already
// present in dp
if(dp[a][b] != -1)
return dp[a][b];
// a is greater
if (a > b)
dp[a][b] = gcd(a-b, b);
// b is greater
else
dp[a][b] = gcd(a, b-a);
// return dp
return dp[a][b];
}
// Driver program to test above function
let a = 98, b = 56;
for(let i = 0; i < 1001; i++) {
for(let j = 0; j < 1001; j++) {
dp[i][j] = -1;
}
}
document.write("GCD of "+ a + " and " + b + " is " + gcd(a, b));
// This code is contributed by Samim Hossain Mondal
</script>
C++
// C++ program to find GCD of two numbers
#include <iostream>
using namespace std;
// Recursive function to return gcd of a and b in single line
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
// Driver program to test above function
int main()
{
int a = 98, b = 56;
cout<<"GCD of "<<a<<" and "<<b<<" is "<<gcd(a, b);
return 0;
}
C
// C program to find GCD of two numbers
#include <stdio.h>
// Recursive function to return gcd of a and b
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Driver program to test above function
int main()
{
int a = 98, b = 56;
printf("GCD of %d and %d is %d ", a, b, gcd(a, b));
return 0;
}
Java
// Java program to find GCD of two numbers
class Test
{
// Recursive function to return gcd of a and b
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Driver method
public static void main(String[] args)
{
int a = 98, b = 56;
System.out.println("GCD of " + a +" and " + b + " is " + gcd(a, b));
}
}
Python3
# Recursive function to return gcd of a and b
def gcd(a,b):
# Everything divides 0
if (b == 0):
return a
return gcd(b, a%b)
# Driver program to test above function
a = 98
b = 56
if(gcd(a, b)):
print('GCD of', a, 'and', b, 'is', gcd(a, b))
else:
print('not found')
# This code is contributed by Danish Raza
C#
// C# program to find GCD of two
// numbers
using System;
class GFG {
// Recursive function to return
// gcd of a and b
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Driver method
public static void Main()
{
int a = 98, b = 56;
Console.WriteLine("GCD of "
+ a +" and " + b + " is "
+ gcd(a, b));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to find GCD
// of two numbers
// Recursive function to
// return gcd of a and b
function gcd($a, $b)
{
// Everything divides 0
if($b==0)
return $a ;
return gcd( $b , $a % $b ) ;
}
// Driver code
$a = 98 ;
$b = 56 ;
echo "GCD of $a and $b is ", gcd($a , $b) ;
// This code is contributed by Anivesh Tiwari
?>
Javascript
<script>
// Javascript program to find GCD of two number
// Recursive function to return gcd of a and b
function gcd(a, b){
// Everything divides 0
if(b == 0){
return a;
}
return gcd(b, a % b);
}
// Driver code
let a = 98;
let b = 56;
document.write(`GCD of ${a} and ${b} is ${gcd(a, b)}`);
// This code is contributed by _saurabh_jaiswal
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA