Project Euler – Problem 5

Written by on 23 October 2010

Topics: Project Euler

Lets jump right into solving Problem 5 of Project Euler and let me try to give you an answer on how to solve it. The problem formulation is :

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 (divisible with no remainder) by all of the numbers from 1 to 20?

Once again I will provide you with two different solutions and some tips and tricks on how to speed them up a bit.

Brute Forcing

As always we will start out with a brute force approach to it. Which is pretty simple, I make a while loop, and as long as the remainder is different from zero for one of the divisors we increase the number. The solution is:

int i = 1;

while (i %  2 != 0 || i %  3 != 0 || i %  4 != 0 || i %  5 != 0 ||
         i %  6 != 0 || i %  7 != 0 || i %  8 != 0 || i %  9 != 0 ||
         i % 10 != 0 || i % 11 != 0 || i % 12 != 0 || i % 13 != 0 ||
         i % 14 != 0 || i % 15 != 0 || i % 16 != 0 || i % 17 != 0 ||
         i % 18 != 0 || i % 19 != 0 || i % 20 != 0 ){
    i++;
}

and the result is

The smallest number dividable with all number 1-20 is 232792560
Solution took 718,75 ms

Simple right? It works, it takes less than a minute and it is easy to read and write. But it lacks speed. We can rather easily speed it up, since we would need the number to be divisible by 20, we don’t need to check every number, but we can limit it to search in increments of 20. Which makes the code look like:

int i = 20;

while (i %  2 != 0 || i %  3 != 0 || i %  4 != 0 || i %  5 != 0 ||
         i %  6 != 0 || i %  7 != 0 || i %  8 != 0 || i %  9 != 0 ||
         i % 10 != 0 || i % 11 != 0 || i % 12 != 0 || i % 13 != 0 ||
         i % 14 != 0 || i % 15 != 0 || i % 16 != 0 || i % 17 != 0 ||
         i % 18 != 0 || i % 19 != 0 || i % 20 != 0) {
    i += 20;
}

The result is:

The smallest number dividable with all number 1-20 is 232792560
Solution took 125 ms

Quite a speed-up just by making some simple changes with a simple approach to the problem. However, the algorithm still doesn’t scale well, so if we want to increase the divisors from 1-20 to 1-40, it would increase the solution time significantly, so lets look at another approach.

Prime factorisation

In the solution to problem 3 we discussed prime factorisation and we can deduct two important properties we can use for this problem:

  1. All numbers have a unique prime factorisation
  2. All non-prime factors of a number, can be generated from the prime factors

This enables us to restate the problem as

Find the smallest set of primes, such that all numbers 1-20 can be constructed. This set will be the prime factorisation of the smallest number to which 1-20 are all evenly divisible.

Lets build it up step by step. We denote the biggest factor we want to investigate as k, such that we want to find the solution for k=20. Furthermore we define the solution as N.

Lets start by looking at the first few numbers of k.

k=2, N = 2
k = 3, N = 2*3 = 6
k = 4, N = 2*3*2 = 12

The prime factorisation of 4 is 2*2, but we already have one of factors we need from the factorisation of 2. Therefore we only need to add one 2, to find a set of prime factors so we can describe all all numbers 1-4. This goes on until we have reach k=20.

How do we make this into an algorithm?

Let pi be the i’th prime, then N can be expressed as N = p1^a1 * p2^a2 * p3^a3

We start by putting ai = 0 for all i. We can iterate over all the divisors, such that divisor j=1,2,…,20 can be factorised as Nj = p1^b1 * p2^b2 * p3^b3… and then ai = max(ai, bi).

We can factorise each j=1,2,…,20 as we did in Problem 3, or we can investigate the size of ai a bit more. The exponent ai is the largest natural number which result in pi^ai <= k.

For p1 = 2, we have that 2^4=16 and 2^5 = 32. Therefore a1 = 4. In more general terms we can express ai = floor(log k/ log pi).

So under the assumption that we have the primes, we can rather easily find the exponents, needed to express N. First thing we need to find is a list of primes, which can be found as:

private int[] generatePrimes(int upperLimit){
List<int> primes = new List<int>();
    bool isPrime;
    int j;

    primes.Add(2);

    for (int i = 3; i <= upperLimit; i += 2) {
        j = 0;
        isPrime = true;
        while (primes[j]*primes[j] <= i) {
            if (i % primes[j] == 0) {
                isPrime = false;
                break;
            }
            j++;
        }
        if (isPrime) {
            primes.Add(i);
        }
    }

    return primes.ToArray<int>();
}

We check all odd numbers, and see if they are divisible with an already found prime, until we reach the square root of the number. If no prime divisor is found, then the number is also a prime. It is a pretty efficient algorithm which builds on many of the principles we are already using.

Now that we have a method for finding our primes, we can also make the algorithm which can be written as:

int divisorMax = 20;
int[] p = generatePrimes(divisorMax);
int result = 1;

for (int i = 0; i < p.Length; i++) {
int a = (int) Math.Floor(Math.Log(divisorMax) / Math.Log(p[i]));
    result = result * ((int)Math.Pow(p[i],a));
}

which gives the result

The smallest number dividable with all number 1-20 is 232792560
Solution took 15,625 ms

A bit more complicated to write, but a lot more efficient to run, especially if we increase k.

Wrapping up

I hope the explanation was understandable, otherwise let me know, and I will try to update the explanation. I have uploaded the source code if you are curious, you can download here.

28 Comments For This Post I'd Love to Hear Yours!

  1. Bill says:

    just wanted to let you know that I am still working through your blog. I also noticed the Functional Fun blog you linked too. I’m enjoying it as well.

  2. SuprDewd says:

    Another method to solving this problem is calculating lcm(1..20):

    int gcd(int a, int b)
    {
    	while (b != 0)
    	{
    		a %= b;
    		a ^= b;
    		b ^= a;
    		a ^= b;
    	}
    
    	return a;
    }
    
    int lcm(int a, int b)
    {
    	return a / gcd(a, b) * b;
    }
    
    int main()
    {
    	int res = 1;
    	for (int i = 2; i <= 20; i++)
    	{
    		res = lcm(res, i);
    	}
    
    	printf("%d\n", res);
    	return 0;
    }
  3. Kristian says:

    Hi SuprDewd

    Yes that is indeed another way of solving this problem. It seems that there are a whole lot of ways to do this. The solution you propose seems to me as the most intuitive method today. It wasn’t when I wrote the post though.

    /Kristian

  4. Nusrat says:


    public class Problem5LCM {

    public static void main(String args[]){
    long result = 2L;
    for(int i=3;i=b)
    return gcd(b,a%b);
    else
    return gcd(a,b%a);
    }
    }

  5. Kristian says:

    Hi Nusrat

    I think your code got messed up by the blog. Can you please repost it with [code] [/code] tags around it instead?

  6. sapun24 says:

    i think that this way of writing a code is a pain in the ass and it is easy to make a mistake (e.g. type error where you mistakenly write 18 instead of 19 and etc)

    this is the way i wrote it in only one minute:

    #include<iostream>
    using namespace std;
    int main()
    {
        long t;
        int i,brojac;
        for(t=21;t<2147483646;t++)
        {
            for(i=1;i<21;i++){
                if (t%i==0) brojac++;
                }
            if (brojac==20){
                cout<<"Broj je: "<<t;
                break;
                }
            brojac=0;
                }
        system("pause");
    }
    

    still, don’t get me wrong, your code is just fine but maybe not practical

    EDIT: sorry for the repost, i did it because of the code

  7. Kristian says:

    I completely agree with you that the first couple of implementations are not practical at all.

    However, I think the last one is actually feasible. And knowing what I know today I would have written part of it differently.

    But anyway, thanks for your suggestion. It is always nice to see other peoples code.

  8. /*
    * To change this template, choose Tools | Templates
    * and open the template in the editor.
    */
    package project_euler;

    /**
    *
    * @author Prince
    */
    public class ProjectEuler {

    /**
    * @param args the command line arguments
    */
    public static void main(String[] args) {
    // TODO code application logic here

    int counter = 1, i = 2, val = 0;

    // Sup smallest positive no. divisible by even nos. within 1-20
    while (true){

    if ( counter % i == 0 ){
    i += 1;
    if( i == 20 )
    val = counter;
    }else {
    counter++ ;
    i = 2;
    }

    if ( i== 20 ) break;
    }
    System.out.println(“”+counter );
    }
    }

  9. John says:

    For your final solution:

    The smallest number dividable with all number 1-20 is 232792560
    Solution took 15,625 ms

    Is that 15,625ms or 15.625ms? I’m assuming the latter.

    Anyway, for brute force I cut out half of the divisor checks as follows:

    int i = 0;
    while (true)
    {
    i += 20;
    if (i % 11 != 0) continue;
    if (i % 12 != 0) continue;
    if (i % 13 != 0) continue;
    if (i % 14 != 0) continue;
    if (i % 15 != 0) continue;
    if (i % 16 != 0) continue;
    if (i % 17 != 0) continue;
    if (i % 18 != 0) continue;
    if (i % 19 != 0) continue;
    return i;
    }

    Completes in 16.5476ms.

  10. Kristian says:

    The whole , vs. . is a matter of language settings I think. In this case it is somewhere between 15 and 16 ms.

  11. jbreezy says:

    i solved this problem by means of analysis and a process of elimination.\

    you know the correct factorization is contained in the factorization of 1*2*3*4…..*20

    first, isolate the primes:

    2 3 5 7 11 13 15 17 19

    list nonprimes:

    4 6 8 9 10 12 14 15 16 18 20

    delete occurrences of lesser nonprimes that exist within the factorization ofother nonprimes(for example, any number divisible by 8 will be divisible by 4. therefore delete 4)

    12 14 15 16 18 20

    now we have 12 14 15 16 18 20; 2 3 5 7 11 13 17 19

    delete occurrences of lesser primes that also exist in the factorization of nonprimes:

    12 14 15 16 18 20; 11 13 17 19

    now we know the number we are looking for is 11*13*17*19*A, where A is made up of the factors of 12 14 15 16 18 20. begin removing unneeded factors from 12 14 15 16 18 20:

    12 14 15 16 18 and 20 need to be present in the prime factorization of A.

    if 12 becomes a 6, 12*14*15*16*18*20 becomes 6*14*15*16*18*20.
    6*14 = 6*2*7 = 12*7 which is obviously divisible by 12. 6 can then become a 3 because there are sufficient 2s in the 16 for 3 to get to 12.

    we can replace 14 with 7 because of the 2s in 16.
    we can replace 15 with 5 because of the 3s in 18.

    now we have 3 7 5 16 18. we can replace 18 with 9 because of the 2s in 16. we can replace that 9 with 3 because of the 3 we already have.

    now we have 3 7 5 16 3 and can go no further.

    considering the primes we left out earlier:
    3 7 5 16 3; 11 13 17 19

    multiply them together and get the answer:

    3*7*5*16*3*11*13*17*19

  12. Pr8 says:

    The exponent ai is the largest natural number which result in .

    Could you explain why this is?

  13. Kristian says:

    I am not sure I can explain it in other terms than I already have.

  14. Michael J says:

    got the time down to about .2-.5 ms

  15. Chris says:

    I’ve been workin on optimizing an implimentation of the prime factorization method. I’ve got it running at very nearly the speed of the lcm method posted by SuprDewd. The difference between 10,000 iterations of each using 40 instead of 20 is only about .25 seconds.

    After these tests, I think the lcm method is just the better way to solve the problem, at least as far as speed goes.

  16. Jack says:

    This is my code. It is a modification of the sieve of Eratosthenes. I couldn’t measure the time because it took less than 1 ms to solve.
    int n = 20;
    boolean prime[] = new boolean[n];
    long product = 1;
    for(int i = 2; i <= n; i++){
    if(!prime[i-1]){
    product *= (long)i;
    for(int j = i*i; j <= n; j+=i){
    prime[j-1] = true;
    if(Math.log(j) / Math.log(i)-(int)(Math.log(j) / Math.log(i))== 0){
    product *= i;
    }
    }
    }
    }
    System.out.println(product);

  17. Slguhy says:

    What about 9’699’690 ? it’s smaller than 232’792’560

  18. Fizi says:

    Even I thought about using lcm and it turns out python has a very neat way of doing it. Thanks for the great work btw. Its of immense use to me.

    def f():
    from fractions import gcd
    return reduce(lambda x,y: x*y//gcd(x,y), range(1,21))

  19. Caleb says:

    So, I’m a very basic beginner at c++, but i came up with something i thought was way faster then the method shown above.

    int main(){

    int myArray[] = {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
    long long number = 1000000000;
    for(long long i = 0; i < number; i++ )
    {
    while(i % myArray[0] == 0 && i % myArray[1] == 0 && i % myArray[2] == 0
    && i % myArray[3] == 0 && i % myArray[4] == 0 && i % myArray[5] == 0
    && i % myArray[6] == 0 && i % myArray[7] == 0 && i % myArray[8] == 0
    && i % myArray[9] == 0 && i % myArray[10] == 0 && i % myArray[11] == 0
    && i % myArray[12] == 0 && i % myArray[13] == 0 && i % myArray[14] == 0
    && i % myArray[15] == 0 && i % myArray[16] == 0 && i % myArray[17] == 0
    && i % myArray[18] == 0)
    {
    i++;
    cout << i << endl;
    }

    }

    }

  20. Shahar says:

    Damn… I lost it when you “restate” the problem.

  21. Hi,
    I wrote this solution only with gcd and no lcm.
    time for n=40 was 0ms

    for n=40 in your program, result must long

    tanx

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace euler5
    {
    class Program
    {
    const int n = 20;

    static int gcd(int a, int b)
    {
    int r = a % b;
    if (r == 0)
    return b;
    else
    return gcd(b, r);
    }

    static long problem5()
    {
    int[] l = new int[n + 1];
    for (int i = 1; i <= n; i++)
    l[i] = i;
    long s = 1;
    for (int i = 1; i <= n; i++)
    {
    s *= l[i];
    for (int j = i + 1; j <= n; j++)
    l[j] /= gcd(l[i], l[j]);
    }
    return s;
    }

    static void Main(string[] args)
    {
    int s = Environment.TickCount;
    long t = problem5();
    Console.Write("Answer=" + t);
    Console.Write(" time=" + (Environment.TickCount – s));
    Console.ReadLine();
    }
    }
    }

  22. Yossu says:

    Came across this while seeing how other people solved the problem.

    My C# solution is shorter and faster than any posted here, at just 20 lines (counting the two functions that do the actual work, the Main() method is only there for testing), and solves the problem in under 1ms.

    You can copy this directly into LinqPad (which is where I wrote it) and see…


    void Main() {
    System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
    sw.Start();
    Console.WriteLine (Lcm (20));
    sw.Stop();
    Console.WriteLine (sw.ElapsedMilliseconds + "ms");
    }

    private int Lcm (int n) {
    List<Tuple> primefactors = Enumerable.Range (2, n - 2)
    .SelectMany (i => PrimeFactorsList (i)
    .GroupBy (n1 => n1)
    .Select (g => new Tuple (g.Key, g.Count ())))
    .GroupBy (t => t.Item1)
    .Select (g => new Tuple (g.Key, g.Max (g1 => g1.Item2))
    ).ToList();
    return primefactors.Aggregate (1, (a, pf) => a * (int)Math.Pow (pf.Item1, pf.Item2));
    }

    private List PrimeFactorsList (int n) {
    if (n == 1) {
    return new List();
    } else {
    int a = Enumerable.Range (2, n).First (i => n % i == 0);
    List rest = PrimeFactorsList (n / a);
    rest.Insert (0, a);
    return rest;
    }
    }

    Hope that’s of interest to someone!

  23. Akshat says:

    #include
    #include

    long int lcm(long int n, int m){
    long int a=n, b=m, c=1;
    do{
    c=a%b;
    a=b;
    b=c;
    }while(c>0);
    return (n*m)/a;
    }

    int main(){
    long int lm=2520;
    for(long int i=11;i<=20;i++){
    lm=lcm(lm,i);
    cout<<lm<<endl;
    }
    getch();
    return 0;
    }

    What do you think?

  24. Amit says:

    For Python 3.5, this works fast: functools.reduce(lambda x,y: x*y//math.gcd(x,y), range(1,20+1)). See https://stackoverflow.com/a/147539/832230.

  25. Missaka Iddamalgoda says:

    This is the code I came up with in JAVA I guess it is efficient and to find the Smallest multiple to any number you just have to replace 20 with number you want.

    class smallestMultiple{
    	public static void main(String args[]){
    		long startTime = System.currentTimeMillis();
    		int i = 20; //If you want upto 40 replace 20 with 40
    		boolean status=false;
    		L1 : while (!status){
    			int j=2;
    			L2 : while (j<20){ //Replace here
    				if (i%j!=0)
    					break;
    				j++;
    				if (j==20){ //Replace here
    					status = true;
    					break L1;
    				}
    			}
    			i +=20; //Replace here
    		}
    		System.out.println(i);
    		long endTime   = System.currentTimeMillis();
    		System.out.println(endTime-startTime);
    	}
    }
    

    If you have any suggestions please mail me.

  26. What’s about this function, quiet easily understandable as taught in our childhood in school In maths.

    static void Attempt1()
    {
    long numbers[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20},divisor=2,lcm=1,iterator;
    boolean isAnyDivided=false;
    while(sumOfArrays(numbers)!=20)
    {
    System.out.println(divisor+"="+Arrays.toString(numbers));
    isAnyDivided=false;
    for(iterator=0;iterator<20;iterator++)
    {
    if(numbers[(int)iterator]!=1)
    {
    if(numbers[(int)iterator]%divisor==0)
    {
    numbers[(int)iterator]/=divisor;
    isAnyDivided=true;
    }
    }
    }
    if(isAnyDivided==false)
    divisor++;
    else
    lcm*=divisor;
    }
    System.out.println(lcm);
    }

  27. Mak says:

    if i do not go in depth with math and stick with the brute force one
    we can achieve a fast result


    var i = 2520;
    while (i % 11 != 0 || i % 12 != 0 || i % 13 != 0 ||
    i % 14 != 0 || i % 15 != 0 || i % 16 != 0 || i % 17 != 0 ||
    i % 18 != 0 || i % 19 != 0 || i % 20 != 0 ){
    i = i + 2520;
    }

    node pro5brutforce.js 0.08s user 0.01s system 97% cpu 0.099 total

  28. Vaibhav Wadhwa says:

    I came up with the following code in python. it basically starts with our number as ‘1’ then iterates over a list of numbers from 1-20. It multiplies our resultant with each iteration ‘i’ and divides rest of the numbers in the list with ‘i’ (which are divisible by ‘i’).

    number = 1;
    
    listOfNumbers = [];
    for i in range(1, 20):
        listOfNumbers.append(i);
    
    for i in listOfNumbers:
        number *= i;
        for j in range(0, len(listOfNumbers) - 1):
            if listOfNumbers[j] % i == 0:
                listOfNumbers[j] /= i;
    
    print("The smallest positive number that is evenly divisible by all of the numbers from 1 to 20 is: " + str(number));
    

Trackbacks For This Post

  1. Problem 5 « Project Euler – F# C# LINQ and .NET
  2. Filip Danic | Project Euler #5: Smallest multiple - When BruteForce Actually Works! - Filip Danic

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.