Project Euler in R Problem 5

The goal of this problem was to find the smallest positive number which is evenly divisible by all of the numbers from 1 to 20. In other words, we are looking for the least common multiple of the integers 1 through 20.

I considered a few circuitous routes before I found an efficient method. First I defined a function named “gcd” to find the greatest common divisor of two integers. I simply employed Euclid’s Algorithm for finding GCDs to construct this relatively simple function. I then wrote another short function named “lcm” which finds the least common multiple of two integers by multiplying them and dividing the product by the greatest common divisor of the two (nothing fancy here, I used the basic definition of LCM).

Finally, I created a numeric vector and set the first entry to be 1 (since the least common multiple of 1 and 1 is 1). For spots 2 through 20 I ran a for loop to calculate successive LCMs. For example, the second slot of the “ans” vector was the LCM(1,2), the third slot was LCM(LCM(1,2),3) and so on.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
gcd <- function(a,b) {
 if (a %% b == 0) {
   return(b) }
 else gcd(b, a %% b)
}

lcm <- function(a,b) {
 lcm <-  (a * b) / gcd(a,b)
return(lcm)
}

ans <- numeric()
ans[1] <- lcm(1,1)

for (i in 2:20) {
 ans[i] <- lcm(ans[i-1], i)
}

ans[20]

R is able to return the answer in a few milliseconds using this script.