Editorial

The greatest common divisor (gcd) of two integers is defined as the largest non-negative integer that divides both of these integers. For example, $GCD(8,12)=4$.

It is known that $GCD(0,x)=|x|$ (the absolute value of $x$), because $|x|$ is the largest non-negative integer that divides $0$ and $x$. For example, $GCD(-6,0)=6,GCD(0,5)=5$.

To find the gcd of two numbers, you can use an iterative algorithm: subtract the smaller number from the larger one. When one of the numbers becomes $0$, the other one becomes the gcd. For example, $GCD(10,24)=GCD(10,14)=GCD(10,4)=GCD(6,4)=GCD(2,4)=GCD(2,2)=GCD(2,0)=2$.

If instead of the "subtraction" operation, you use the "modulo" operation, the calculations will proceed significantly faster.

For example, to find $GCD(1,10^9)$ uning subtraction, you would need to perform $10^9$ operations. Using the modulo operation, only one action is required.

The GCD of two numbers can be computed using the formula:

or the same as

The iterative implementation is based on the idea presented in the final recurrence relation:

while (b > 0) :
    compute a = a % b;
    swap the contents of variables a and b;

Algorithm implementation

The gcd function computes the GCD of two numbers.

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

The main part of the program. Read the input data.

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

Compute and print the GCD of two numbers.

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

Algorithm implementation — simplified recursion

The gcd function computes the GCD of two numbers.

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

The main part of the program. Read the input data.

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

Compute and print the GCD of two numbers.

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

Algorithm implementation — iterative

The gcd function computes the GCD of two numbers.

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

The main part of the program. Read the input data.

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

Compute and print the GCD of two numbers.

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

Java implementation

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 implementation — recursion

The gcd function computes the GCD of two numbers.

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)

The main part of the program. Read the input data.

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

Compute and print the GCD of two numbers.

print(gcd(a, b))

Python implementation — gcd

To compute the greatest common divisor (GCD) of two numbers, let's use the gcd function built into the Python language.

import math

Read the input data.

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

Compute and print the GCD of two numbers.

print(math.gcd(a, b))