Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
      • 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
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
      • 17
      • 18
        Graph Representation

  • Least common multiple (LCM)

    The least common multiple of two numbers a and b is the smallest number that is divisible by both a and b. So, we can find a number l (least common multiple) such that and where x and y are positive integers (2 ≤ x, y).
    A naive approach would be to iterate over the multiples of a (1·a, 2·a, 3·a, ...) and see if that number is divisible by b. Yet, this might take too long. Imagine if a and b are 13 and 17. In that case, we should calculate 1·13, 2·13, …, up to 17·13 to finally arrive at a number divisible by both 13 and 17.
    In fact, we can see that a·b is always a common multiple of a and b. Yet, it might not always be the smallest one. In the case of 13 and 17 it was the smallest but in other cases like 8 and 12 it might not. In general, the LCM of a and b is equal to the product of a and b divided by their greatest common divisor:
    The intuition behind the formula lies in the fact that the LCM is the smallest multiple of both numbers that contains all their common prime factors. And, since the greatest common divisor of two numbers is the product of all their common prime factors, the LCM can be found by dividing the product of the numbers by their greatest common divisor to remove the duplicate factors.
    So, to find the LCM of two numbers, we first find the prime factorization of both numbers and then multiply the maximum power of each prime that appears in either of the factorizations.
    Here, the product a·b produces all the prime factors of both a and b with exponents summed up. gcd(a, b) removes the minimum of the exponents from each of the product components, therefore leaving the maximum for each of the factors. That results in exactly the LCM of a and b.


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


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


    8 12
    54 24
    17 16


    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