## oschvr

### a blog about software, programming, business, travelling and life.

**← Problems**

# Smallest multiple

#### 24 days ago

###### 02/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$$

$$gcd(a,b) = gcd(b, a \space mod \space b)$$

And converting it to a recursive function:

`1 2 3 4 5 6 7`

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

`1 2 3`

`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.

`1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28`

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