2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

At first glance, and as a concept refresher, we’ll have to use **GCD* and **LCM**.

  • GCD stands for Greatest Common Divisor. GCD is the largest number that divides the given numbers.
  • LCM stands for Lowest Common Multiple. LCM is the smallest number that is multiple of a and b.

To find the LCM, we can use the following formula:

$$ lcm(a,b) = frac{ | ab | }{gcd(a, b)} $$

But before that, we must find the GCD. For that, we’ll use the Euclid’s algorithm, which consists of an efficient way to calculate the greatest common divisor. The algorithm is described:

$$ gcd(a,0) = a $$

$$ space b) $$

And converting it to a recursive function:

func gcd(a, b int64) int64 {
  c := a % b
  if c == 0 {
    return b
  }
  return gcd(b, c)
}

Then, we can write our simple function to get the LCM:

func lcm(a, b int64) int64 {
  return a * b /gcd(a, b)
}

Finally, we’ll iterate from 1 … 20 starting with 2, and we’ll calculate the Lowest Common Multiplier of every digit.

package main

import (
  "fmt"
  "time"
)

func main() {
  start := time.Now()
  var a, i int64 = 1, 2
  for ; i <= 20; i++ {
    a = lcm(a, i)
  }
  fmt.Println("Execution time: ", time.Since(start))
  fmt.Println("Smallest Multiple: ", a)
}

func lcm(a, b int64) int64 {
  return a * b / gcd(a, b)
}

func gcd(a, b int64) int64 {
  c := a % b
  if c == 0 {
    return b
  }
  return gcd(b, c)
}

Execution time: 1.416µs

Answer#

Smallest Multiple: 232792560