DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’» is a community of 966,904 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
Cover image for Project Euler - Problem 1 - Multiples Of 3 And 5
Jingles (Hong Jing)
Jingles (Hong Jing)

Posted on • Originally published at jinglescode.github.io

Project Euler - Problem 1 - Multiples Of 3 And 5

The problem

This is problem 1 from the Project Euler.

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below the provided parameter value number.


Let's begin

Initialise variables and common functions:

var test_number = 8456; // this number we wanna test

// this function execute the code and records the time to execute
function run_function(func) {
  var t0 = performance.now();
  console.log('Output:', func);
  var t1 = performance.now();
  console.log("Took " + (t1 - t0) + " milliseconds.");
}

Attempt #1: recursive functions

Personal challenge, I always enjoy stretching myself with recursive functions, so here is my take on this problem with a recursive function.

function multiplesOf3and5(number) {
  number = number - 1;
  var list_numbers = []
  list_numbers = multiplesOfN(list_numbers, number, 3);
  list_numbers = multiplesOfN(list_numbers, number, 5);
  return list_numbers.reduce((a, b) => a + b, 0)
}

function multiplesOfN(list_numbers, number, n) {
  if(number > 0 && number%n==0 && !list_numbers.includes(number)) {
    list_numbers.push(number);
    return multiplesOfN(list_numbers, number-n, n);
  }else if(number > 0){
    return multiplesOfN(list_numbers, number-1, n);
  }else{
    return list_numbers;
  }
}

run_function(multiplesOf3and5(test_number));

The output:

Output: 16687353
Took 0.5999999993946403 milliseconds.

Hmmm, but if the test number is 19564, recursive functions will overflow:

RangeError: Maximum call stack size exceeded

Attempt #2: for-loop

Go back to the good old for-loop:

var sum = 0;
function multiplesOf3and5_b(number) {
  for(var i = 1; i < number; i++){
    if((i % 3 === 0 )||(i % 5 === 0)){
      sum = sum + i;
    }
  }
  return sum;
}

run_function(multiplesOf3and5_b(test_number));

The output:

Output: 16687353
Took 0.045000000682193786 milliseconds.

Works great for test number 19564:

Output: 89301183
Took 0.6550000034621917 milliseconds.

The recursive method overflow at bigger test case and good old for-loop is more efficient. Can it be any better?

I just began my Project Euler Challenge journey; anyone wants to do this together? It will be fun and we can learn a thing or two by solving this problem in different ways.

Top comments (0)

Classic DEV Post from 2020:

js visualized

πŸš€βš™οΈ JavaScript Visualized: the JavaScript Engine

As JavaScript devs, we usually don't have to deal with compilers ourselves. However, it's definitely good to know the basics of the JavaScript engine and see how it handles our human-friendly JS code, and turns it into something machines understand! πŸ₯³

Happy coding!