Project Euler – Problem 5

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 = 23 = 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.

Posted by Kristian

33 comments

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.

[…] here is an approach based on prime factorization. Look here for a proper […]

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;
}

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


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);
}
}

Hi Nusrat

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

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

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.

/*
* 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 );
}
}

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.

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

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

The exponent ai is the largest natural number which result in [latex]pi^ai <= k[/latex].

Could you explain why this is?

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

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

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.

[…] don’t get me wrong, I still did it the proper way thanks to a brilliant post that I found on mathblog.dk which explained the mathematical concepts that I was missing. But, this did get me thinking […]

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);

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

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))

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;
}

}

}

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

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();
}
}
}

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!

#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?

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.

Missaka Iddamalgoda

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.

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);
}

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

Vaibhav Wadhwa

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));

I know this is old but I thought I’d contribute my solution in F#. Here is the thought process:

The only numbers evenly divisible by 2 are 2itself and its multiples. Taking this number sequence and finding the first number divisible by 3 in it, one obtains the smallest number evenly divisible by 2 and 3. Taking the sequence of this number and its multiples and finding the first number divisible by 4, one obtains the smallest number evenly divisible by 2, 3 and 4. And so on…

This is relatively straightforward to encode using sequences:

let narrowDown m n s =
    (s, {m .. n})
    ||> Seq.fold (fun a i ->
        let j = Seq.find (fun x -> x % i = 0) a
        Seq.initInfinite (fun i -> (i + 1) * j))

let euler005 () =
    Seq.initInfinite (fun i -> i + 1)
    |> narrowDown 2 20
    |> Seq.head

However, the runtime is abysmally slow:

> let r, t = stopwatch euler005;;
val t : System.TimeSpan = 00:00:00.0152158
val r : int = 232792560

Therefore I got rid of the sequences, and coded the same algorithm as a loop (modeled by a recursive function):

let narrowDown s i m n =
    if m > n then s
    elif s % m = 0 then narrowDown s s (m + 1) n
    else narrowDown (s + i) i m n

let euler005 () = narrowDown 2 2 2 20

This is about a hundred times faster:

> let r, t = stopwatch euler005;;
val t : System.TimeSpan = 00:00:00.0001552
val r : int = 232792560

def is_prime(n):
s=0
if n==2 or n==3 or n==5:
return True
elif n==1 or n%2==0:
return False
else :
for i in range(2,n//2):
if n%i==0:
return False
return True
product=1
for i in range(1,21):
j=1
if is_prime(i):
while j<21:
j=i
product
=(j//i)
print(product)

Leave a Reply