Рубрики

Программа для поиска GCD или HCF из двух чисел

GCD (наибольший общий делитель) или HCF (наибольший общий фактор) из двух чисел — это наибольшее число, которое разделяет их оба.

Например, GCD 20 и 28 — 4, а GCD 98 и 56 — 14.

Простое решение состоит в том, чтобы найти все простые факторы обоих чисел, а затем найти пересечение всех факторов, присутствующих в обоих числах. Наконец вернуть произведение элементов в пересечении.

Эффективным решением является использование евклидова алгоритма, который является основным алгоритмом, используемым для этой цели. Идея состоит в том, что GCD из двух чисел не изменяется, если меньшее число вычитается из большего числа.

C ++

// C ++ программа для поиска GCD из двух чисел
#include <iostream>

using namespace std;

// Рекурсивная функция для возврата gcd из a и b

int gcd(int a, int b)

{

    // Все делит 0

    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);

}

   
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int a = 98, b = 56;

    cout<<"GCD of "<<a<<" and "<<b<<" is "<<gcd(a, b);

    return 0;

}

С

// C программа для поиска GCD из двух чисел
#include <stdio.h>

  
// Рекурсивная функция для возврата gcd из a и b

int gcd(int a, int b)

{

    // Все делит 0

    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);

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int a = 98, b = 56;

    printf("GCD of %d and %d is %d ", a, b, gcd(a, b));

    return 0;

}

Джава

// Java программа для поиска GCD из двух чисел

class Test

{

    // Рекурсивная функция для возврата gcd из a и b

    static int gcd(int a, int b)

    {

        // Все делит 0

        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);

    }

      

    // Метод драйвера

    public static void main(String[] args) 

    {

        int a = 98, b = 56;

        System.out.println("GCD of " + a +" and " + b + " is " + gcd(a, b));

    }

}

python3

# Рекурсивная функция для возврата gcd из a и b

def gcd(a,b):

      

    # Все делит 0

    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')

  
# Этот код предоставлен Danish Raza

C #

// C # программа для поиска GCD из двух
// числа

using System;

  

class GFG {

      

    // Рекурсивная функция для возврата

    // gcd of a и b

    static int gcd(int a, int b)

    {

          

        // Все делит 0

        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);

    }

      

    // Метод драйвера

    public static void Main() 

    {

        int a = 98, b = 56;

        Console.WriteLine("GCD of " 

          + a +" and " + b + " is " 

                      + gcd(a, b));

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// PHP программа для поиска GCD
// из двух чисел

  
// Рекурсивная функция для
// вернуть gcd из a и b

function gcd($a, $b)

{

  

    // Все делит 0

    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 ;

  

echo "GCD of $a and $b is ", gcd($a , $b) ;

  
// Этот код предоставлен Anivesh Tiwari
?>


Выход:

GCD of 98 and 56 is 14

Более эффективное решение — использовать оператор по модулю в евклидовом алгоритме .

C ++

// C ++ программа для поиска GCD из двух чисел
#include <iostream>

using namespace std;

// Рекурсивная функция для возврата gcd из a и b

int gcd(int a, int b)

{

    if (b == 0)

        return a;

    return gcd(b, a % b); 

      
}

   
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int a = 98, b = 56;

    cout<<"GCD of "<<a<<" and "<<b<<" is "<<gcd(a, b);

    return 0;

}

С

// C программа для поиска GCD из двух чисел
#include <stdio.h>

  
// Рекурсивная функция для возврата gcd из a и b

int gcd(int a, int b)

{

    if (b == 0)

        return a;

    return gcd(b, a % b); 

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int a = 98, b = 56;

    printf("GCD of %d and %d is %d ", a, b, gcd(a, b));

    return 0;

}

Джава

// Java программа для поиска GCD из двух чисел

class Test

{

    // Рекурсивная функция для возврата gcd из a и b

    static int gcd(int a, int b)

    {

      if (b == 0)

        return a;

      return gcd(b, a % b); 

    }

      

    // Метод драйвера

    public static void main(String[] args) 

    {

        int a = 98, b = 56;

        System.out.println("GCD of " + a +" and " + b + " is " + gcd(a, b));

    }

}

python3

# Рекурсивная функция для возврата gcd из a и b

def gcd(a,b):

      

    # Все делит 0

    if (b == 0):

         return a

    return gcd(b, a%b)

  
# Программа драйвера для проверки вышеуказанной функции

a = 98

b = 56

if(gcd(a, b)):

    print('GCD of', a, 'and', b, 'is', gcd(a, b))

else:

    print('not found')

  
# Этот код предоставлен Danish Raza

C #

// C # программа для поиска GCD из двух
// числа

using System;

  

class GFG {

      

    // Рекурсивная функция для возврата

    // gcd of a и b

    static int gcd(int a, int b)

    {      

       if (b == 0)

          return a;

       return gcd(b, a % b); 

    }

      

    // Метод драйвера

    public static void Main() 

    {

        int a = 98, b = 56;

        Console.WriteLine("GCD of " 

          + a +" and " + b + " is " 

                      + gcd(a, b));

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// PHP программа для поиска GCD
// из двух чисел

  
// Рекурсивная функция для
// вернуть gcd из a и b

function gcd($a, $b)

{

    // Все делит 0

    if($b==0)

        return $a ;

  

    return gcd( $b , $a % $b ) ;

}

  
// Код драйвера

$a = 98 ;

$b = 56 ;

  

echo "GCD of $a and $b is ", gcd($a , $b) ;

  
// Этот код предоставлен Anivesh Tiwari
?>


Выход:

GCD of 98 and 56 is 14

Пожалуйста, обратитесь к GCD более двух (или массиву) чисел, чтобы найти HCF более двух чисел.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Программа для поиска GCD или HCF из двух чисел

0.00 (0%) 0 votes