Project Euler Problem #5 - Smallest Multiple (in Python)

  1. # 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
  2. # What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? */

  4. # returns smallest multiple that is evenly divisible by all numbers from 1 - n
  5. # returns -1 if multiple does not exist
  6. def findSmallestMultiple(n):
  7.     for i in range(n, factorial(n) + 1, n):
  8.         if isMultiple(i, n):
  9.             return i
  10.     return -1

  12. # checks every number between 1 and n to see if x is a multiple of every number
  13. # returns True if x is found to be a multiple of every number, and False if x is
  14. # found to not be a multiple of any number
  15. def isMultiple(x, n):
  16.     for i in range(1, n):
  17.         if x % i != 0:
  18.             return False
  19.     return True

  21. # returns the n factorial, or -1 if it does not exist
  22. def factorial(n):
  23.     if n > 1: return n * factorial(n - 1)
  24.     elif n >= 0: return 1
  25.     else: return -1

  27. print (findSmallestMultiple(10)) # 2520
  28. print (findSmallestMultiple(20))
DOWNLOAD

If you're running Python 2.x, the code above will fail for the second call of the function because the for-loop range will "contain too many items".
In that case, use the code below (while-loop instead of for-loop). If you're running Python 3.x, the code above will work just fine. 

  1. # 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
  2. # What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? */

  4. # returns smallest multiple that is evenly divisible by all numbers from 1 - n
  5. # returns -1 if multiple does not exist
  6. # works up to n = 20 (long reaches maximum value for values > 20) */
  7. def findSmallestMultiple(n):
  8.     i = n
  9.     while i < factorial(n):
  10.         if isMultiple(i, n):
  11.             return i
  12.         i += n
  13.     return -1

  15. # checks every number between 1 and n to see if x is a multiple of every number
  16. # returns True if x is found to be a multiple of every number, and False if x is
  17. # found to not be a multiple of any number */ 
  18. def isMultiple(x, n):
  19.     for i in range(1, n):
  20.         if x % i != 0:
  21.             return False
  22.     return True

  24. # returns the n factorial, or -1 if it does not exist
  25. def factorial(n):
  26.     if n > 1: return n * factorial(n - 1)
  27.     elif n >= 0: return 1
  28.     else: return -1

  30. print (findSmallestMultiple(10)) # 2520
  31. print (findSmallestMultiple(20))
DOWNLOAD

              Created: February 16, 2014
Completed in full by: Michael Yaworski