Розбір

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

Найбільшим спільним дільником (НСД) двох цілих чисел називається найбільше натуральне число, яке ділить ці числа. Наприклад, НСД(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))