Recursive greatest common divisor P42523


Statement
 

pdf   zip   main.cc   main.c   main.java   main.py

thehtml

Write a recursive function that computes the greatest common divisor of two natural numbers a and b using the fast version of the Euclidean algorithm.

Interface

C++
int gcd(int a, int b);
C
int gcd(int a, int b);
Java
public static int gcd(int a, int b);
Python
gcd(a, b) # returns int
 
gcd(a: int, b: int) -> int

Precondition

Neither a nor b are negative, and at least one of them is strictly greater than zero.

Observation You only need to submit the required procedure; your main program will be ignored.

Public test cases

  • Input/Output

    gcd(66, 12) → 6
    gcd(100, 21) → 1
    gcd(0, 10) → 10
    • Information
    Author
    Jordi Petit
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C C++ Java Python
    User solutions
    C C++ Java Python