princeofsudan

ProjectEuler#5 Smallest multiple

Mar 2nd, 2013
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.89 KB | None | 0 0
  1. #2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
  2.  
  3. #What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
  4.  
  5. #Algorithm from http://en.wikipedia.org/wiki/Least_common_multiple
  6. #A simple algorithm section
  7.  
  8. primes=[2,3,5,7,11,13,17,19]
  9. myRange = range(1,21)
  10.  
  11. def checkOnes(l):
  12.     for i in range(len(l)):
  13.         if l[i] != 1:
  14.             return False
  15.     return True
  16.  
  17. def checkDev(l,p):
  18.     for i in range(len(l)):
  19.         if l[i]%p == 0:
  20.             return True
  21.     return False
  22.  
  23. x = []
  24. i = 0
  25. while not checkOnes(myRange):
  26.     while checkDev(myRange,primes[i]):
  27.         x.append(primes[i])
  28.         for j in range(len(myRange)):
  29.             if myRange[j] % primes[i] == 0:
  30.                 myRange[j] = myRange[j] / primes[i]
  31.     i += 1
  32.  
  33. ans = 1
  34. for k in x:
  35.     ans *= k
  36.  
  37. print ans
Advertisement
Add Comment
Please, Sign In to add comment