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
Collapse
 
dwayne profile image
Dwayne Crooks • • 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.

Collapse
 
alainvanhout profile image
Alain Van Hout •

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.

Collapse
 
karataev profile image
Eugene Karataev •

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.

Thread Thread
 
alainvanhout profile image
Alain Van Hout •

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.

Thread Thread
 
karataev profile image
Eugene Karataev •

+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.

Thread Thread
 
dwayne profile image
Dwayne Crooks • • 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).

Collapse
 
aspittel profile image
Ali Spittel •

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))
Collapse
 
maxart2501 profile image
Massimo Artizzu •

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

Collapse
 
1258632 profile image
by •

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

Collapse
 
tweedoriginal profile image
TWEEDOriginal •

Can you please explain your code

Collapse
 
karataev profile image
Eugene Karataev •

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]));
Collapse
 
crownedprinz profile image
Ademola John •

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

Collapse
 
karataev profile image
Eugene Karataev •

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

code snippet

const yourCode = 'here';
Thread Thread
 
crownedprinz profile image
Ademola John •

Thannk you so much Eugene. This gave me tough time

Collapse
 
flrnd profile image
Florian Rand • • Edited

Here's mine

C

#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)
}
Collapse
 
jay profile image
Jay •

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)
    }
}
Collapse
 
khouloudzaiter profile image
khouloudzaiter •

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);
    }
}
Collapse
 
natonathan profile image
Nathan Tamez •

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
Collapse
 
thorstenhirsch profile image
Thorsten Hirsch • • 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. 😄

Collapse
 
prabh profile image
Prabhjot Singh Rana •

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)
Collapse
 
engosama69 profile image
engosama69 • • 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()

Collapse
 
cyberbot143 profile image
Sai krishna V • 

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
Collapse
 
_andy_lu_ profile image
Andy Lu •

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