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

Question

Problem description:

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?

Least Common Multiple(LCM):

In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, usually denoted by lcm, is the smallest positive integer that is divisible by both a and b.

Example:

LCM(6,7,21)

Multiples of 6: 6, 12, 18, 24, 30, 36, 42, 48, 54, 60

Multiples of 7: 7, 14, 21, 28, 35, 42, 56, 63

Multiples of 21: 21, 42, 63

Find the smallest number that is on all of the lists. We have it in bold above.

So LCM(6, 7, 21) is 42

The best solution with Euclid GCD algorithm

Euclid’s GCD algorithm:

1- The smallest positive number that is evenly divided (divided without remainder) by a > set of numbers is called the Least Common Multiple (LCM).

2- All we have to do to solve this problem is find the LCM for the integers {1, 2, 3, 4, > …, 20} using Euclid’s GCD algorithm.

3- After some reflection you might correctly realize that every integer is divisible by > > 1, so 1 can be removed from the list and use 2 through 20 instead.

4- we can eliminate other factors as well.

5- We leave 20 in the calculation but then remove its factors {2, 4, 5, 10}. Any number > > evenly divisible by 20 is also evenly divisible by these factors.

6- 19 is prime and has no factors— it stays.

7- 18 has factors {2, 3, 6, 9} and we already removed 2 but we can remove 3, 6, and 9. 17 > is prime — it stays.

8- We continue this numeric carnage until our original list of {1…20} becomes the much > > smaller {11…20}.

9- In general, all smaller factors of a bigger number in the list can be safely removed > > without changing the LCM.

My Solution

This is my solution for problem 5 of Project Euler using Python:

 def LCM(a, b):  
    '''Return the least common multiple of
       the specified integer arguments
    '''
    return a // gcd(a, b) * b  
N = int(input("The LCM for numbers 1 through "))
N_reduce = reduce(LCM, range(N//2+1, N+1))
print ("The LCM for numbers 1 through" ,N, "is:", N_reduce)

Answer 1

Straight.

If you
- defined "the range-LCM" in a function with a docsting
- presented imports
 and test cases or usage examples,
- added boundary checks (try N = 0),
I'd call it great.

You might get a reviewer's extra eye-roll throwing in

def largest_power_of_two_not_exceeding(n):
    """ Return the largest power of 2 not exceeding n taken as an integer. """
    n = int(n)
    if n <= 0:
        raise ValueError
    while 0 != n & n-1:
        n &= n-1
    return n

def LCMup2(n):
    """ return the LCM for numbers 1 through n. """
    n = int(n)
    if n <= 1:
        return 1
    return reduce(LCM, range((n//6)*2+1, n+1, 2)
                  ) * largest_power_of_two_not_exceeding(n)