Module: (Python) Subroutines: Procedures and Functions - 2


Problem

4/8

Euclid's algorithm

Theory Click to read/hide

Euclid's algorithm

Euclid's algorithm — efficient BC" title="Algorithm">Algorithm To Find Greatest Common Divisor  two Integers (or general measures  two Lines). The algorithm is named after Greek Math Euclid (3rd century B.C. ), who first described it in VII and X books «Beginnings". It is one of the oldest numerical algorithms in use today.

Remember the math.

Greatest common divisor of two natural numbers (gcd) is the largest natural number by which they are divisible.

For example, the numbers 12 and 18 have common divisors: 2, 3, 6. The greatest common divisor is 6. This is written as: gcd(12, 18) = 6

In programming, there are several implementations of the Euclid algorithm. Here is a description of one of them in the form of a block diagram.


Try to implement this algorithm.

Problem

Write a function that calculates the gcd of two numbers.


Input
The input string contains two natural numbers separated by a space – a and b .

Imprint
The program should output one natural number: GCD of the given numbers.

 

Examples
# Input Output
1 14 21 7


time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
Python
Write the program below 
a, b = map(int, input().split())
print(NOD(a,b))

     

Program check result

To check the solution of the problem, you need to register or log in!