Skip to main content

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

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
Labels:

Popular posts from this blog

Making a quiz web app with python and flask

Edit : When you are creating a web app with h tml templates, then y ou will have to sa ve the html file in templates folder in the Current Wor ki ng Directory( CWD). If you save the file in the C W D directl y you will get a TemplateNotFound error. Thank you Udhay for pointing it out.   In this post we will create a quiz website using python . I will be using the flask framework . After reading this tutorial you will learn form submission , flask templates , python code in flask templates , shuffling the questions and options with the random module and few others.  Please note that this tutorial is not big as it seems to be. Some of the code has been rewritten to maintain consistency and also font size is somewhat big so that your eyes won't get stressed reading this tutorial. Also the content has not occupied the full width of the page. In this tutorial I am assuming that you are having a very basic understanding of the flask framework . Please refer the documentation
Read more

Problem 11 Project Euler Solution with python

Largest product in a grid In the 20×20 grid below, four numbers along a diagonal line have been marked in red. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07
Read more

Problem 60 Project Euler Solution with python

Prime pair sets The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property. Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime. This problem is j u st a brute force problem. If you have come here because you don't know the limit upto which you will h ave to gener ate the prime numbers t hen go ahe ad and t r y with 10,000 . When I first start ed solving the problem I chose 1 million(beca use most of the problem s on project E uler have this limit ), but it took very long for the computer to fin d the solution. After searching on the internet then I found many people choosing 10, 000 so I have changed my in put f rom 1 million to 10000 and the output was f ast. He
Read more