Get the smallest positive number that is divisible by all numbers from 1 to 20

Question

I made a code in a way that works, but it doesn’t look anything pythonic, and takes a lot of time.

i = 1
numero = 1
while i != 0:
    if numero % 1 == 0 and numero % 2 == 0 and numero % 3 == 0 and numero % 4 == 0 and numero % 5 == 0 and numero % 6 ==\
            0 and numero % 7 == 0 and numero % 8 == 0 and numero % 9 == 0 and numero % 10 == 0 and numero % 11 == 0\
              and numero % 12 == 0 and numero % 13 == 0 and numero % 14 == 0 and numero % 15 == 0 and numero % 16 == 0 \
              and numero % 17 == 0 and numero % 18 == 0 and numero % 19 == 0 and numero % 20 == 0:
        print(numero)
        i = 0
    else:
        numero += 1

How could I improve this code?

Answer 1

Basically what you want is to calculate the MMC (common minimum multiple) between these numbers. So it’s more of a mathematical question than pythonic. Suffice it to consider that:

1. for 3 numbers x, y and z, the MMC(x, y, z) is the same as MMC(MMC(x, y), z) (which is also the same as MMC(x, MMC(y, z))). That is, we can calculate the MMC of 2 in 2 numbers until we reach the final result
2. one of the many ways to calculate is MMC(x, y) = x * y / MDC(x, y) (where MDC is the maximum common divisor)

Even Python 3.8 you can use the function math.gcd to calculate the MDC, then just use it to calculate step 2. And for step 1, just do a loop in the numbers and go calculating the MMC between them:

from math import gcd

def mmc(numeros):
    m = 1
    for n in numeros:
        m = m * n // gcd(m, n)
    return m

numeros = range(2, 21)
print(mmc(numeros)) # 232792560

I used range(2, 21) (all numbers between 2 and 20), as it makes no sense to include the 1 (all numbers are multiples of 1 and it is redundant to include it in the calculation).

From Python 3.9 you can use math.lcm to calculate the MMC directly, without needing the above formula:

from math import lcm

print(lcm(*range(2, 21))) # 232792560

Detail that the numbers of range has to be passed via unpacking (with the asterisk before the range), so that the numbers are passed as parameters (without the asterisk, the actual range is passed as a parameter and then does not work).

---

Of course you can optimize a little more because you don’t need to have all the numbers in the list. It could just be:

###########################################
# Até Python 3.8
from math import gcd

def mmc(numeros):
    m = 1
    for n in numeros:
        m = m * n // gcd(m, n)
    return m

print(mmc([11, 13, 14, 15, 16, 17, 18, 19, 20]))

###########################################
# A partir de Python 3.9
from math import lcm

print(lcm(11, 13, 14, 15, 16, 17, 18, 19, 20)) # 232792560

If the number is multiple of 20, it will surely also be multiple of 2, 4, 5 and 10, if it is multiple of 18, it will surely also be of 2, 3, 6 and 9, and so on. And since it is a multiple of 3 and 4, it will also be 12, etc. So you don’t need to have everyone on the list.

---

Another option is to use functools.reduce, which makes the code shorter (but not necessarily easier to understand, varies according to each person’s opinion):

from math import gcd
from functools import reduce

def mmc(numeros):
    return reduce(lambda x, y: x * y // gcd(x, y), numeros)

But this only for Python <= 3.8 as from version 3.9 just pass all numbers to math.lcm, without the need to use reduce.