DEV Community

Project Euler #5 - Finding the Smallest Multiple

Peter Kim Frank on May 29, 2019

Continuing the wonderful community solutions to Project Euler. This is Problem 5, finding the smallest multiple. 2520 is the smallest number tha...

Read full post

Dwayne Crooks • May 29 '19 • Edited

Here's mine via paper and pencil. The primes less than 20 are 2, 3, 5, 7, 11, 13, 17 and 19. The LCM of 1,2,3,...,20 is 16*9*5*7*11*13*17*19.

Alain Van Hout • May 29 '19

That's the only proper way to do it. A software developer's job is to solve problems, ideally as efficiently as is possible and/or as is practical. That may or may not include writing code.

Eugene Karataev • May 30 '19

I really like "make it work, then make it fast" approach.
First implement a naive solution that works, then make it fast if necessary.
Starting out with the attitude of best solution possible might be very time consuming.

Alain Van Hout • May 30 '19

I'm not really talking about premature optimization here (on that, I completely agree). It's of course always a balance, because you don't want to get caught in analysis paralysis. But in general I'd say it's still better to 'think before you act'. Otherwise you might be devoting a lot of time and energy to creating and then maintaining a complex solution while a simple one would have sufficed.

Eugene Karataev • May 30 '19

+1 for 'think before you act'.

I wrote my initial comment because of the phrase 'That's the only proper way to do it.' which I disagree with.

Let's return to the initial problem from the post.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

There are no other requirements about code complexity, performance or anything else. Dwayne's solution is clever, but it requires a domain knowledge to understand what's going on. Moreover, it's less flexible for the case of different inputs.
A naive bruteforce solution is definitely slower, but the code intention is clear from the code itself and doesn't require some implicit wisdom.

So, I think both solutions are good and solve the problem. A concrete project's requirements is the most important part when choosing one solution over another.

Dwayne Crooks • May 30 '19 • Edited

Did you notice that all the posted solutions required the same domain knowledge?

If all the numbers from 1 to 20 divide the number then the number must be a multiple of all the numbers from 1 to 20.

Since we want the smallest such number it follows that we want the least common multiple of the numbers from 1 to 20.

Everyone has to make a similar deduction in order to even begin writing their solution.

Rather than writing a program to solve it I simply went ahead and did the LCM calculation by hand. The only extra domain knowledge required is knowing how to calculate the LCM of a set of numbers using prime factorization.

As much as I'd like to take credit for a clever solution, I must say that the prime factorization method is the standard way one learns to find LCM. (LCM using prime factorization)

The way I went about my explanation must have made the solution seem clever but my intention there was to describe a thinking pattern one might go through if they don't know much about LCM and how you'd reason your way from an initial answer (1*2*...*20) to the smallest possible answer.

Also, everyone else used the fact that LCM(a,b)*GCD(a,b) = a*b so that LCM(a,b)=(a*b)/GCD(a,b). Now that's not obvious, unless you look it up or you know why it's true which is based on prime factorization (which in itself is a nice proof, though that's beside the point).

Eugene Karataev • May 30 '19

I like your way of thought and clean explanation.
It's great when you can think deeply about the problem and find a solution without writing a line of code.

But there's also another way. Just convert the problem from the human language to the programming language and throw it to the computer to calculate the result.

What's better? It depends on the environment, because both solutions have their own pros and cons.

Alain Van Hout • May 30 '19 • Edited

@Eugene: I should have elaborated what I meant with 'the only proper way'. I wasn't referring to the fact that Dwayne's solution was analytical/mathematical. I was pointing to the fact that he first analysed the problem before coming up with a solution. This has the benefit of often choosing simpler solutions over complex ones. Indeed, there was no explicit requirement for simplicity (or performance), but then maintainability never tends to be explicitly mentioned in requirements.

Dwayne's logic is essentially the following:

I need the smallest/simplest number divisible by all the numbers in the range (i.e 1->20)
Many numbers in that (or any) range are already divisible by others in that range, so all I need are the prime numbers
So I need to multiple all the prime numbers in that range

Note that the logic here is very straightforward and definitely not complex, is very flexible since it isn't limited to the range of the original requirement, can easily be amended when new requirements are added, and can in the future still be implemented as code when things go beyond simple arithmetic (with the added bonus that the choice of programming language is still entirely open).

As to domain knowledge, probably the most important lesson that most developers learn at some point is that domain knowledge is the cornerstone to success, and that knowing when and how to acquire it is an invaluable skill. To put it another way: the most productive software developers proactively talk to (domain expert) people and learn from them.

(though, as Dwayne mentioned, the domain knowledge here is quite limited. I would expect/hope that anyone who attempts this knows the concept of prime numbers, since it's so tightly coupled with the concept of divisibility).

Eugene Karataev • May 30 '19

Let's follow your algorithm for the range 1 to 10 (for simplicity).
Numbers in this range: 1,2,3,4,5,6,7,8,9,10.
Prime numbers in this range: 2,3,5,7.
Multiplication of these numbers: 2*3*5*7 = 210. Which is different from the correct answer 2520, so your algorithm is wrong.

Sometimes it's better to write a simple, stupid algorithm and let a computer to do the heavy work instead of doing all the work in your brain, which might be complicated and error prone.

Dwayne Crooks • May 30 '19 • Edited

Huh? That's not the algorithm.

You misunderstood. The explanation I gave is one of many ways someone can DISCOVER that what you need to do is to find the LCM of the numbers.

You do agree that the problem is implicitly asking you to find the LCM of 1,2,3,...,20?

Once you reach that point of understanding then you can do at least two things:

You can write a program that finds you the LCM. As all the coded solutions do.
You can use prime factorization to quickly compute the answer. As I did and it boils down to finding the highest powers of the primes in the given range which would be 2*2*2, 3*3, 5 and 7.

And I don't disagree with you. Start with brute force and improve. You'd then have something to test your optimizations, clever code etc against.

Dwayne Crooks • May 30 '19

So I need to multiple all the prime numbers in that range

Not exactly. You need to multiply by the highest powers of the primes in the range.

Eugene Karataev • May 30 '19

You do agree that the problem is implicitly asking you to find the LCM of 1,2,3,...,20?

Yes.
And as you mentioned there are at least two ways to solve the problem. Both are valid.

And I don't disagree with you. Start with brute force and improve. You'd then have something to test your optimizations, clever code etc against.

We're on the same page 😉

Florian Rand • May 29 '19

If you like efficient and practical solutions, here:
Using mathematica

Apply[LCM, Range[20]]

Alain Van Hout • May 29 '19

Or the more generic solution of that kind: google.com/search?q=euler+5+answer

Florian Rand • May 29 '19

🌈🦄

Alain Van Hout • May 29 '19

😁

Mary Thompson • May 29 '19

I wish I could understand this answer. It looks simple. I love software development, but I am horrible with math. Simple addition gives me anxiety.

Dwayne Crooks • May 29 '19

Hey Mary, let me help you understand this answer.

But first.

This problem as do most problems on Project Euler requires domain knowledge in Mathematics. In particular, Prealgebra. You can become a good software developer without knowing lots of Math. Furthermore, the types of problems you'd encounter on Project Euler won't prepare you for developing reliable, maintainable, user-friendly software. In short, don't get discouraged. Learn the domain knowledge on an as needed basis as the requirements of your software demands. And my last bit of advice is to read A Mind for Numbers - How to Excel at Math and Science if you want help getting over that math anxiety.

Here goes.

Start with a smaller problem. In this case, the example given is small enough and we can use it to check our answer.

What is the smallest positive number that is divisible by all of the numbers from 1 to 10?

Let's ignore 1 because every positive number is divisible by 1.

A positive number that's divisible by 2,3,...,10 is 2*3*...*10 because 2,3,...,10 are all factors of that number.

But is it the smallest? No and here's a simple reason why we might think so by looking at the powers of 2.

2, 4 and 8 are all factors of 2*3*...*10. But since 2 and 4 are factors of 8 it follows that 2, 4 and 8 will also be factors of 3*5*6*7*8*9*10. So we found a smaller number that works.

Similar reasoning leads us to smaller and smaller numbers in the following way.

Since 3 is a factor of 9 it follows that 3 and 9 will still be factors of 5*6*7*8*9*10.

Look at this. 5 is a factor of 10. So should we get rid of the 5 and leave the 10? 5 is a factor but so is 2. But 2 is already accounted for by the 8. Because of this we leave the 5 and remove the 10.

We're now left with 5*6*7*8*9.

8 accounts for 2, 4 and 8.
9 accounts for 3 and 9.
5 accounts for 5.

And the number is divisible by 10 because it is divisible by 2 and 5.

What about 6 and 7?

6 divides 5*7*8*9 so we can leave it out. However, 7 must remain since 7 does not divide 5*8*9. Therefore, we are left with: 5*7*8*9=(2*2*2)*(3*3)*5*7.

If you follow similar reasoning for the larger case you'd get the answer that I got.

What you'd notice is that all you're doing is finding the least common multiple of all the numbers and that's why you see the coded solutions are calculating LCM.

Mary Thompson • May 30 '19

I dont know how to do the quote format.. this is my first issue though: "A positive number that's divisible by 2,3,...,10 is 2*3*...*10 because 2,3,...,10 are all factors of that number." I don't understand how one came up with that conclusion and by divisible you mean without a remainder? Is it because you multiplied them all together that dividing by one of the numbers puts you in the same place you started before multiplying?

"But since 2 and 4 are factors of 8 it follows that 2, 4 and 8 will also be factors of 3*5*6*7*8*9*10." I have no idea how this "follows"; same with 3 and 5... esp. 5 because you remove 10 instead. Why didn't you remove 9 instead of 3? This is not confusing at all.

And why does "6 divide 5*7*8*9" but "7 does not divide 5*8*9"? Did you do the math to determine this or can this be explained without trial and error?

There are still assumptions in this solution, but thanks for trying to explain, though.

And I've already ordered that Math and Science book. Thank you.

Dwayne Crooks • May 30 '19

Is it because you multiplied them all together that dividing by one of the numbers puts you in the same place you started before multiplying?

Yes.

I have no idea how this "follows".

3*5*6*7*8*9*10 = 3*5*6*7*(2*4)*9*10 => 2, 4 and 8 are factors.

If 10 = 2*5 then 2 and 5 are factors. So that's what I'm doing above.

Why didn't you remove 9 instead of 3?

If I removed 9 then 9 would no longer be a factor of what remains. There's no way to make a 9 with what remains.

And why does "6 divide 5*7*8*9"

Because we can take a 2 from 8 and a 3 from 9 to show that 6 is a factor, i.e. 5*7*8*9 = 5*7*4*(2*3)*3 = 5*7*4*6*3.

but "7 does not divide 5*8*9"

5*8*9 = 5*2*2*2*3*3, see no 7's :).

Mary Thompson • May 31 '19

I see. This makes more sense. Thank you.

Dwayne Crooks • May 31 '19

You're welcome.

1adityas • Apr 1 '20

hey but in euiler project pdf there is another more efficient algorithm is given .. can you explain me that please?

Ali Spittel • May 29 '19

Here's mine!

def greatest_common_denominator(a, b):
    while b:      
        a, b = b, a % b
    return a


def least_common_multiple(a, b):
    return (a * b) / greatest_common_denominator(a, b)


def least_common_multiple_range(li):
    if len(li) == 2:
        return least_common_multiple(li[0], li[1])
    else:
        check = li.pop()
        return least_common_multiple(check, least_common_multiple_range(li))


print least_common_multiple_range(range(1, 21))

Massimo Artizzu • May 29 '19

The most significant part here is that you can compute the least common multiple by computing the greatest common denominator and using it to divide the product of the two numbers.

I was about to propose a similar solution (in JavaScript) but yours is sufficient 👍
(Yes, the language itself isn't important for me. Just the mathematical challenge.)

by • Jan 14 '20

Please do propose your version in javascript. Certainly it will not be excessive

TWEEDOriginal • Jan 15 '20

Can you please explain your code

Eugene Karataev • May 29 '19

Bruteforce node solution 🤣

const assert = require('assert');

console.clear();

function findSmallestMultiple(numbers) {
  function isDividable(num) {
    for (let i = numbers.length - 1; i >= 0; i--) {
      if (num % numbers[i] !== 0) return false;
    }
    return true;
  }

  let counter = 1;
  while (true) {
    if (isDividable(counter)) break;
    counter++;
  }
  return counter;
}

// assert(findSmallestMultiple([7,8,9,10]) === 2520);

console.log(findSmallestMultiple([11,12,13,14,15,16,17,18,19,20]));

Ademola John • May 18 '20

Please how do i put my code in this snippet like you did when i want to comment with my own answer

Eugene Karataev • May 18 '20

Wrap your content with three backtics to render it as a code snippet.

const yourCode = 'here';

Ademola John • May 18 '20

Thannk you so much Eugene. This gave me tough time

Florian Rand • May 29 '19 • Edited

Here's mine

#include <stdio.h>

unsigned long gcd(unsigned long a, unsigned long b) {
 while (a != 0) {
   unsigned long c = a;
   a = b % a;
   b = c;
 }
 return b;
}

unsigned long lcm(unsigned long a, unsigned long b) {
  return a * ( b / gcd(a, b) );
}

int main () {
  unsigned int i = 2;
  unsigned long result = 1;
  for (i = 2; i < 20; i++) {
    result = lcm(result, i);
  }
  printf("%d\n", result);
}

And Go

package main

import (
    "fmt"
)

func gcd(a, b int64) int64 {
    for b != 0 {
        a, b = b, a%b
    }
    return b
}

func lcm(a, b int64) int64 {
    return a * (b / gcd(a, b))
}

func main() {
    var result, i int64 = 1, 2
    for ; i <= 20; i++ {
        result = lcm(result, i)
    }
    fmt.Println(result)
}

Jay • May 29 '19

Rust Solution Playground

fn main() {
    println!("{}", get_number(1, 20))
}

fn get_number(start: usize, end: usize) -> u32 {
    (start..end).fold(1_u32, |acc, n| lcm(acc, n as u32))
}

fn lcm(a: u32, b: u32) -> u32 {
    (a * b) / gcd(a, b)
}

fn gcd(a: u32, b: u32) -> u32 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

khouloudzaiter • Aug 5 '19

I like solving it via paper and pencil, but it is always a pleasure to do some code :)
Java code:

public class Problem5 {

    public static void main(String[] args) {
        int max = 20;
        int n = (int) (Math.pow(max,2) -1);
        boolean smallestNumberEvenDivisible = false;
        //int i = 2;

       while( !smallestNumberEvenDivisible ){
           n++;
           int i = 2;
           boolean allDivisible = true;
                while ( i<=max && allDivisible){
                    allDivisible = n%i ==0;
                    i++;
                }
           smallestNumberEvenDivisible = allDivisible;
        }
        System.out.println(n);
    }
}

Nathan Tamez • May 30 '19

Here is my solution. it's not the cleanest but is quite fast and it seems to work. I used nodeJS

function checkDivisible(number) {
  if (
    number % 20 == 0 &&
    number % 19 == 0 &&
    number % 18 == 0 &&
    number % 17 == 0 &&
    number % 16 == 0 &&
    number % 15 == 0 &&
    number % 14 == 0 &&
    number % 13 == 0 &&
    number % 12 == 0 &&
    number % 11 == 0 &&
    number % 10 == 0 &&
    number % 9 == 0 &&
    number % 8 == 0 &&
    number % 7 == 0 &&
    number % 6 == 0 &&
    number % 5 == 0 &&
    number % 4 == 0 &&
    number % 3 == 0 &&
    number % 2 == 0 &&
    number % 1 == 0
  ) {
    return true;
  } else {
    return false;
  }
}

function main() {
  let done = false;
  let c = 1;
  console.log(`c = ${c}, incrment = ${c}`);
  let startTime = Date.now();
  while (!done) {
    if (checkDivisible(c)) {
      console.log(`${c} is Divisible by 1 - 20 with no remainder`);
      done = true;
    }
    c++;
  }
  let endTime = Date.now();
  console.log(`Time Taken: ${Math.round(endTime - startTime)}ms`);
}
main();

here is the output

c = 1, incrment = 1
232792560 is Divisible by 1 - 20 with no remainder
Time Taken: 607ms

Thorsten Hirsch • May 30 '19 • Edited

Perl 6 has an lcm operator (no modules/libraries necessary):

say [lcm] 1..20;

I guess you won't find a solution shorter than this one. However I doubt that this makes Perl 6 attractive. The more features the language has, the more you have to learn. If you master it, it sure is fun to write code like this or the next example:

say [+] grep * %% (3|5), ^1000;

It's a solution for Euler#1 and it's another example that the language has a ton of features that enable you to write super short code. Unfortunately it also gets harder to read, some might even call it gibberish.

But you can also write beautiful code in Perl 6. Here are solutions for Project Euler Problems, super-short ones as well as beautiful ones. 😄

Prabhjot Singh Rana • Feb 5 '20

My solution in Python:

result = 1
num = 20
list1 = []
list2 = []
index1= True

for i in range(2,num+1):
    list1.append(i)

while len(list1) > 0:

    a = list1[0]

    for i in list1:
        if index1 == True:
            index1 = False
            result = result * i
            continue
        else:
            if i%a != 0:
                list2.append(i)
            else:
                list2.append(i/a)

    index1 = True

    list1 = list2[:]
    list2 = []

print(result)

engosama69 • Mar 9 '20 • Edited

smallest number that can be divided by each of the numbers from 1 to 10 without any remainder

for smallest_num in range(1, 1000000):
check_list = []
for x in range(1, 11):
if smallest_num % x == 0:
check_list.append(x)
check_list.sort()
if check_list == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]:
print("Smallest Number is : ", smallest_num)
exit()

Sai krishna V • Aug 31 '19


const oneTo20Array = Array.from({ length: 20 }, (_, i) => i + 1);

const isDivisibleByOneTo20 = num => oneTo20Array.every(cur => num % cur === 0);

let isFound = false,
  minDiv = 19;

do {
  ++minDiv;
  if (isDivisibleByOneTo20(minDiv)) isFound = true;
} while (!isFound);

console.log(minDiv); //2327925600

Andy Lu • May 30 '19

Clojure

(defn euler-5 [x]
  (let [gcd (fn [x y] (if (zero? y) x (recur y (mod x y))))
        lcm (fn [x y] (/ (* x y) (gcd x y)))]
    (reduce lcm (range 1 (inc x)))))