НСД двох чисел (Розбір)

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

Основна частина програми. Читаємо вхідні дані.

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

Обчислюємо і виводимо НСД двох чисел.

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

Реалізація алгоритму — цикл

Функція gcd обчислює НСД двох чисел.

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

Основна частина програми. Читаємо вхідні дані.

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

Обчислюємо і виводимо НСД двох чисел.

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

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 реалізація — рекурсія

Функція gcd обчислює НСД двох чисел.

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