Editorial

Algorithm Analysis

The greatest common divisor (GCD) of two integers is defined as the greatest natural number that divides both numbers. For example, GCD(8, 12) = 4.

It is known that GCD(0, $x$) = $|x|$ (the absolute value of $x$), since $|x|$ is the greatest natural number that divides 0 and $x$. For example, GCD(-6, 0) = 6, GCD(0, 5) = 5.

To find the GCD of two numbers, one can use an iterative algorithm: subtract the smaller number from the larger one. When one of the numbers becomes 0, the other 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 the modulus operation is used, the calculation will be much faster.

For example, to find the GCD(1, $10^9$) using subtraction would require $10^9$ operations. Using the modulus operation requires only one action.

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

The cyclic implementation is based on the idea presented in the last recurrent relation:

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

Algorithm Implementation

The function gcd calculates 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);

Calculate and display the GCD of two numbers.

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

Algorithm Implementation – Simplified Recursion

The function gcd calculates the GCD of two numbers.

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

Algorithm Implementation – Loop

The function gcd calculates 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;
}

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

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 Implementation – gcd

To calculate the GCD of two numbers, we will use the gcd function built into Python.

import math

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