"""5. 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?"""
list=[]
possibility_list=[]
base=1
numberlist=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
for number in numberlist:
    for iteration in range(1000):
        list.append(iteration*number)
for possibility in list:
    if list.count(possibility)==20:
        print("Found LCM of [1:21] -->", str(possibility))
        possibility_list.append(possibility)
    else: continue
print(min(possibility_list))

I am currently trying to solve Euler Problem #5, which wants to find the LCM of numbers 1-20. The code above is brute force, but for some reason it doesn't work. Can someone point me in the right direction?

CodePudding user response：

numberlist = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]


def is_prime(num: int) -> bool:
    for factor in range(2, num):
        if num % factor == 0:
            return False
    return True


prime_list = list(filter(is_prime, numberlist))
additional_factor_prime = []
for number in numberlist:
    temp_factor_list = [*prime_list]   additional_factor_prime
    temp_number = number
    for index in range(len(temp_factor_list) - 1, -1, -1):
        if temp_number in prime_list:
            break
        cur_factor = temp_factor_list[index]
        if temp_number % cur_factor == 0:
            temp_factor_list.pop(index)
            temp_number //= cur_factor
    if temp_number not in temp_factor_list and temp_number != 0 and temp_number != 1:
        additional_factor_prime.append(temp_number)

factor_list = [*prime_list]   additional_factor_prime
LCM = 1
for number in factor_list:
    LCM *= number
print(LCM)

CodePudding user response：

As of python 3.9 you can compute the least common multiple directly:

from math import lcm

print(lcm(*range(1, 11)))

If that's "cheating", start with a loop like this:

from math import lcm

result = 1
for i in range (1, 10):
    result = lcm(result, i)

Then replace lcm with gcd. The two-arg version of gcd (greatest common divisor) has been around since python 3.5:

from math import gcd

result = 1
for i in range (1, 10):
    result *= i // gcd(result, i)

Now gcd is something that's relatively easy to implement using Euclid's algorithm. The idea is that if the GCD of two numbers x and y is g, then x = a * g and y = b * g, with a, b relatively prime. If a and b weren't relatively prime, you could divide them by their common multiple and multiply g by that amount. Let's say a >= b. If x is a multiple of y, b must be 1 (again, a and b are relatively prime) and therefore y = g. Otherwise, c = a - b must be relatively prime to both a and b (else they all have a common factor). We can therefore repeat the same reasoning for y and z = x - y until the two numbers become multiples of each other. The sequence must converge because the numbers decrease with every subtraction:

def gcd(x, y):
    if x < y:
        x, y = y, x
    if x % y == 0:
        return y
    return gcd(x - y, y)

result = 1
for i in range (1, 10):
    result *= i // gcd(result, i)

You can probably make this more efficient, but this should be sufficient to form an understanding of how to solve the problem.

A non-recursive GCD could be implemented as

def gcd(x, y):
    while True:
        if x < y:
            x, y = y, x
        if x % y == 0:
            return y
        x -= y