0
\$\begingroup\$

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 by all of the numbers from 1 to 20?

Feel like I went about this the wrong way, but my gut said to check if a number divided evenly by each number up to 20 and when it did, return it.

function isDivisible(number) {
    for (d = 1; d <=20; d++) {
        if (number % d === 0) {
            continue;
        } else {
            return false;
        }
    }
    return true;
}

var number = 1;
do {
    number++;
} while (! isDivisible(number));

console.log(number);
\$\endgroup\$

3 Answers 3

Reset to default
2
\$\begingroup\$

Well, it works. Better algorithms will be given in the discussion list on the Project Euler site, so I'll just look at JavaScript style.

    for (d = 1; d <=20; d++) {

For consistency, there should be a space in <= 20.

        if (number % d === 0) {
            continue;
        } else {
            return false;
        }

When the code skipped by continue is so short, it's more readable to invert the condition and remove the continue:

        if (number % d !== 0) {
            return false;
        }
\$\endgroup\$
2
\$\begingroup\$

You can speed this up a bit in a at least 3 ways, first you can start at a better number.

At minimum, the number will be the product of all the prime factors below 20, 2*3*5*7*11*13*17*19 = 9699690 This number however is not divisible by 20, so we can add 10 more and make it 9699700 which is the next number divisible by 20.

Because of this instead of checking each number you can check every 20th number. (number +=20) You may be able to iterate by 19*20 by picking a better starting number but I am not entirely sure. :)

Thirdly, because the number 1-10 are factors of the number 11-20, you only need to check 11-19 for 0 remainder. 4 and 8 are factors of 16, so if it is divisible for 16 is is also divisible by 4 and 8. We can also skip 20 because we are iterating by it. 

function isDivisible(number) {
    for (let d = 11; d < 20; d++) {
        if (number % d !== 0) {return false;}
    }
    return true;
}

let number = 9699700;
do {
    number+=20;
} while (! isDivisible(number));

console.log(number);
\$\endgroup\$
3
  • \$\begingroup\$ Ok, I checked my math and I think that you can change the starting number to 2*3*5*7*11*13*17*19 * 2 = 19399380 which should be the lowest number divisible by all primes and 20. Starting there you can iterate by number += 19*20 and find the answer. \$\endgroup\$ Commented Jun 28, 2019 at 6:57
  • 1
    \$\begingroup\$ I like this suggestion. At heart, it is saying "Don't just run a big loop and let the computer do the hard work, but think about the problem that you're trying to solve." As it happens, you can go further and count the number of times each prime needs to appear: 2 has to appear four times (to be a multiple of 16), and 3 has to appear twice (to be a multiple of 9). In fact I think that with that, you can actually avoid the whole loop and calculate the answer in one shot. \$\endgroup\$ Commented Jun 28, 2019 at 7:02
  • \$\begingroup\$ You are correct :D \$\endgroup\$ Commented Jun 28, 2019 at 7:05
1
\$\begingroup\$

Least that can be done for deficiency is pick the number as even

var number = 2;

number += 2;
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.