$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 (divisible with no remainder) by all of the numbers from $1$ to $20$?
This problem can be solved by taking the prime factors of all the numbers from $1$ to $20$ and using them to find the least common multiple.
$1 : 1$
$2 : 2$
$3 : 3$
$4 : 2^2$
$5 : 5$
$6 : 2 * 3$
$7 : 7$
$8 : 2^3$
$9 : 3^2$
$10 : 2 * 5$
$11 : 11$
$12 : 2^2 * 3$
$13 : 13$
$14 : 2 * 7$
$15 : 3 * 5$
$16 : 2^4$
$17 : 17$
$18 : 2 * 3^2$
$19 : 19$
$20 : 2^2 * 5$
$-> 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19 $
pow(2, 4) * pow(3, 2) * 5 * 7 * 11 * 13 * 17 * 19
232792560
Another clever way to solve this for the range $1$ to $x$ would be to find all of the primes less than or equal to than $x$, find out each prime's maximum exponent less or equal to $x$, then multiplying all of those numbers together to find their least common multiple.
import math
def isPrime(n):
if n == 1 or n == 2:
return True
elif n > 1:
# check for factors
for i in range(2,n):
if (n % i) == 0:
return False
return True
else:
return False
def primesLessThan(x):
i = 2
primeList = []
while(i <= x):
if (isPrime(i)):
primeList.append(i)
i += 1
return primeList
num = 20
primeList = primesLessThan(num)
powList = [0] * len(primeList)
print(primesLessThan(num))
for i in range(0, len(primeList)):
for j in range(1, math.floor(math.sqrt(num)) + 1):
if (pow(primeList[i], j) <= num):
powList[i] = j
print(powList)
lcm = 1
for i in range(0, len(primeList)):
lcm = lcm * pow(primeList[i], powList[i])
print("The least common multiple of all numbers less than ", num, " is ", lcm)
[2, 3, 5, 7, 11, 13, 17, 19] [4, 2, 1, 1, 1, 1, 1, 1] The least common multiple of all numbers less than 20 is 232792560