Euler Problem 5 – Smallest Multiple

Smallest multiple

Problem 5

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?

 

smallest_multiple <- function(maxnumber) {
num1 = maxnumber
num = maxnumber
flag = TRUE
j = 2
while(flag) {
for(i in 2:maxnumber) {
if (num %% i != 0) {
num = num1 * j
j = j + 1
break
}
}
if (i == maxnumber) {
flag = FALSE
print(num)
}
}
}

smallest_multiple(20)
#[1] 232792560

 

 

The logic here is we take a number in multiples of largest number (here 20) to reduce the number of times we have to check a code. Now we need to check if it is divisible by all the numbers below the max number (20). We do this by checking if mod is equal to 0. We can definitely optimize this further by finding out factors of bigger number. Any number which is divisible by 20 is also divisible by 10, 4, and 2 so we can ignore such steps. We can do this for many other numbers as well.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s