Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • GCD - Euclid’s algorithm

    After running several iterations of the algorithm, we start to notice that there are some redundant operations, and the algorithm of finding the greatest common divisor can actually be optimized.
    With subtraction, we keep subtracting the smaller number from the larger number until we get a result of 0 or a number that is equal to the GCD. We can speed that up by finding the remainder of the larger number divided by the smaller one. With the modulo operation, we keep dividing the larger number by the smaller number and taking the remainder until the remainder is 0. The last non-zero remainder we get is the GCD.
    Think of the modulo operation as a more efficient way of finding the GCD. Instead of subtracting the smaller number from the larger number repeatedly, you are using division to reduce the larger number. This means that you are dividing both numbers by their common divisors and so converging to the greatest common divisor much faster.
    a, b = int(input()), int(input())
    while a > 0 and b > 0:  # In case a or b is 0 => the other one is the GCD
    	a, b = b, a % b       # gcd of (a, b) is the same as gcd of (b, a % b)
    
    d = b if a == 0 else a  # if a is 0 => b is GCD, if b is 0 => a is GCD
    print('gcd:', d)
    This algorithm was first mentioned in Euclid’s book written in 300 BC.
     
    Let’s run several simulations of the algorithm:
    a = 8, b = 12
    1. a = 12, b = 8
    1. a = 8, b = 4
    1. a = 4, b = 0
    1. break ⇒ GCD = 4
    a = 54, b = 24
    1. a = 24, b = 6
    1. a = 6, b = 0
    1. break ⇒ GCD = 6
    a = 17, b = 16
    1. a = 16, b = 1
    1. a = 1, b = 0
    1. break ⇒ GCD = 1

    Input

    The only line of the input contains two integers a and b (0 ≤ a, b ≤ ).

    Output

    The program should print the greatest common divisor of a and b.

    Examples

    Input
    Output
    8 12
    4
    54 24
    6
    17 16
    1

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue