# Smallest multiple

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$$

$$gcd(a,b) = gcd(b, a \space mod \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**