Разбор

Анализ алгоритма

Наибольшим общим делителем (НОД) двух целых чисел называется наибольшее натуральное число, которое делит эти числа. Например, НОД(8, 12) = 4.

Известно, что НОД(0, $x$) = $|x|$ (модуль числа $x$), так как $|x|$ является наибольшим натуральным числом, которое делит 0 и $x$. Например, НОД(-6, 0) = 6, НОД(0, 5) = 5.

Для нахождения НОД двух чисел можно воспользоваться итеративным алгоритмом: следует вычитать меньшее число из большего. Когда одно из чисел станет равным 0, второе станет равным НОД. Например: НОД(10, 24) = НОД(10, 14) = НОД(10, 4) = НОД(6, 4) = НОД(2, 4) = НОД(2, 2) = НОД(2, 0) = 2.

Если вместо операции ‘вычитания’ использовать операцию взятия модуля, то вычисления пройдут значительно быстрее.

Например, для нахождения НОД(1, $10^9$) в случае использования вычитания следует совершить $10^9$ операций. При использовании операции взятия модуля достаточно одного действия.

НОД двух чисел можно вычислить по формуле:

Циклическая реализация состоит в идее, приведенной в последнем рекуррентном соотношении:

пока (b > 0) :
    вычисляем a = a % b;
    меняем местами содержимое переменных a и b;

Реализация алгоритма

Функция gcd вычисляет НОД двух чисел.

int gcd(int a, int b)
{
    if (a == 0) return b;
    if (b == 0) return a;
    if (a >= b) return gcd(a % b, b);
    return gcd(a, b % a);
}

Основная часть программы. Читаем входные данные.

scanf("%d %d",&a,&b);

Вычисляем и выводим НОД двух чисел.

d = gcd(a,b);
printf("%d\n",d);

Реализация алгоритма – упрощенная рекурсия

Функция gcd вычисляет НОД двух чисел.

int gcd(int a, int b)
{
    return (!b) ? a : gcd(b,a % b);
}

Реализация алгоритма – цикл

Функция gcd вычисляет НОД двух чисел.

int gcd(int a, int b)
{
    while (b > 0)
    {
        a = a % b;
        int temp = a; a = b; b = temp;
    }
    return a;
}

Java реализация

import java.util.*;

public class Main
{
    static int gcd(int a, int b)
    {
        if (a == 0) return b;
        if (b == 0) return a;
        if (a >= b) return gcd(a % b, b);
        return gcd(a, b % a);
    }
    
    public static void main(String[] args)
    {
        Scanner con = new Scanner(System.in);
        int a = con.nextInt();
        int b = con.nextInt();
        int res = gcd(a, b);
        System.out.println(res);
        con.close();
    }
}

Python реализация – рекурсия

def gcd(a, b):
    if a == 0: return b
    if b == 0: return a
    if a > b: return gcd(a % b, b)
    return gcd(a, b % a)

a, b = map(int, input().split())
print(gcd(a, b))

Python реализация – gcd

Для вычисления НОД двух чисел воспользуемся функцией gcd, встроенной в языке Питон.

import math

a, b = map(int, input().split())
print(math.gcd(a, b))