## oschvr

### a blog about software, cloud computing, security, money, business, travelling and life.

**← Problems**

# Smallest multiple

#### 1 min

#### over 1 year ago

###### 07/05/2019

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