Problem 5 Projecteuler.net Matlab Smallest Factor

Problem5-projecteuler.net

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?

Solution

The solution for this problem is very simple. I have thought of the solution using prime factorization but my program has become so big which is not really necessary for solving this problem and I was unable to make it small using the looping system. If anyone can write a program using the prime factorization technique you are welcome and please post your solution in the comment below so that others can get benefited, Finally I have found a solution on a website written in c#, and I have converted that solution to Matlab.

Solution 2

First of all Thanks to Olubukola Ogunsola, who has commented/suggested/requested this solution.

Before we continue with the algorithm, remember that in the question you are asked to find the Least Common Multiple(LCM) of numbers from 1 to 20.

There is only one thing, one has to notice about LCM to understand the program. LCM is commutative.

So LCM(a,b,c) = LCM(LCM(a,b), c). The same has been used in the program. I have used the inbuilt lcm function. Have a look at the Program 2 for a better and simple program.

Program

%this program will find find the value of the smallest multiple of the
%given range

%here we have considered the range from 1 - 20
i = 20;
while(rem(i,2) ~= 0 || rem(i,3) ~= 0 || rem(i,4) ~= 0 || ...
        rem(i,5) ~= 0 || rem(i,6) ~=0 || rem(i,7) ~= 0 || rem(i,8) ~= 0 ...
         || rem(i,9) ~= 0 || rem(i,10) ~= 0 || rem(i,11) ~= 0 ...
          || rem(i,12) ~= 0  || rem(i,13) ~= 0  || rem(i,14) ~= 0 ...
           || rem(i,15) ~= 0 || rem(i,16) ~= 0 || rem(i,17) ~= 0 ...
            || rem(i,18) ~= 0 || rem(i,19) ~= 0 || rem(i,20) ~= 0)
        i = i+20;
end
fprintf('The smallest number divisible by the numbers in range of 1-20 is %d\n' ...
    ,i);

Get the matlab file for the above program from here: smallestfactor.m

Program 2

% LCM of 1 and 2
l = lcm(1,2);

% for loop for generating 3-20
for a = 3:20 
% commutative law of LCM
   l = lcm(l, a);
end

%printing the value
l

Explanation:

Approach 1

Before we continue about the explanation about the program you need to know about few things:

1) OR

2) while loop

Here first we will start a variable with a variable equal to 20. We have started with 20 because, every number below 20 will not satisfy the condition. In the same way the next 20 numbers will also do the same and the same follows upto infinity. In the while loop we will check whether the number is divisible by all the numbers from 2 to 20. If not then we will increase the number with 20(because of the sequence explained above) and this will continue until the given number is divisible by all the numbers from 2 to 20(1 was omitted because all the numbers are divisible by 1). Finally we will arrive at a stage where all the numbers are divisible by that number and it is the answer. finally the fprintf function will print the answer for us in a beautiful format. 

Note that " ... " in matlab tells the computer that we will continue the same program line in the next line and consider the next line in the same line.

This program has been taken from projecteuler.net and can be found here: problem 5

You can also download this post and read it offline from here: problem5-projecteuler_matlab.pdf

The above code was formatted using hilite.me

References:
1)   Creating a new variable in each iteration...
2)  Count number of specific values in matrix
3) Number of Nonzero elements in matrix - nnz function in Matlab

I have tried to explain it as easy as possible. Please let me know if you want any more explanation or changes in the program.

Try to solve the program in your way and share it below

Run the program and comment below the output you are getting for a given input.

Keywords: problem 5, projecteuler.net, smallest factor