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

Question

This is a Project Euler challenge where I'm trying to find the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

The logic while I came up with seems to run really slowly. It's been running for the last 4 mins and still hasn't found the number. I'm trying to figure out a) Is this logic correct? b) Why does this take so long? and c) Could someone give me a hint on an alternate logic that is more efficient.

# 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?
smallest_num = 2520
while smallest_num >= 2520:
    divisor = 2
    while smallest_num % divisor == 0 and divisor < 21:
        print("Smalles num = {} and Divisor = {}").format(smallest_num, divisor)
        divisor += 1
    smallest_num += 1
print("Smallest number is: {}").format(smallest_num)

This is still processing and so far my terminal looks like this

You could probably optimize it so that it doesn't check every number between 1 and 20. For example, by checking 20 you are also checking 1, 2, 4, 5, and 10. — rivermont, May 28 '17 at 15:04
There's no reason why `while smallest_num >= 2520:` would ever stop, so no, your logic is not correct. Also the reason you're given the 2520 is so that you can first test your logic on the smaller problem. Try writing a program that doesn't contain 2520, but produces 2520 as the output when considering the numbers from 1 to 10. — Alex Hall, May 28 '17 at 15:07
For programming loops it is often best to by hand write out what will happen to the variables for the first few iterations. This can often diagnose problems about whether the loop will ever stop or achieve its goal — Robb, May 28 '17 at 15:11
You're looking for the least common multiple, and this brute force method is the worst way. What you want to do is prime factorization. https://en.wikipedia.org/wiki/Least_common_multiple Or use Euclid's Algorithm, find the GCD and do some division. — James Poag, May 28 '17 at 15:21

Brad Solomon · Answer 1 · 2017-05-28T15:35:07.807

Here's your method run "properly" (using the term liberally), but as @James mentioned it will take an egregious amount of time as a loop.

divisors = np.arange(1, 21)
num = 2520
while True:
    if np.all(num % divisors == 0):
        print(num)
        break
    num += 1

A much better method (for Python 3.x). Directly from a similar question:

import functools
import math

functools.reduce(lambda x,y: x*y//math.gcd(x, y), range(1, 21))
Out[27]: 232792560

score 1 · Answer 2 · answered May 28 '17 at 16:34

The following code works fine.

#!/usr/bin/env python
import math

#Generating primes
divisorMax = 20;

top = divisorMax + 1 #divisor max is the upper limit

p = [x for x in range(2,top)]

for num in p:
  for idx in range(2,(top//num)+1):
    if num*idx in p:
      p.remove(num*idx)

#Solving the problem
result = 1;

for i in range(0, len(p)):
    a = math.floor(math.log(divisorMax) / math.log(p[i]));
    result = result * (p[i]**a);

print(result)

You are using brute force technique to calculate the number, which is easy to understand and write, but takes very much time.

I am using the Prime Factorisation technique explained here.

olisch · Answer 3 · 2017-05-28T15:50:38.560

i am not 100% sure, if my solution is really correct, but i guess it is and it is pretty fast.

First of all, we don't need to care for all divisors, as most are multiples of each other. So best way is to count the divisors backwards, for example starting with 20 down to 1.

I had a look at the prime numbers, the solution needs to be a multiple of all primes above 10, furthermore we need to check the 20 divisor, the rest can be ignored, as when testing divisor 18, the 9 will work as well, and so on.

So i mulitplied 11 * 13 * 17 * 19 * 20. The resulting is 923780 and is divisible by at least the primes + 20.

So i would start at 923780 and test only every 923780th number.

smallest_num = 923780
steps = 923780
while True:
    divisor = 19
    while smallest_num % divisor == 0 and divisor > 10:
        print("Smalles num = {} and Divisor = {}").format(smallest_num, divisor)
        divisor -= 1
    if divisor == 10:
        print("Smallest number is: {}").format(smallest_num)
        break
    smallest_num += steps

Maybe i have logical error?!

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

3 Answers3