“Проект Эйлер №5” относится к проблеме с веб-сайта Проекта Эйлера. Постановка задачи следующая:

“2520 — это наименьшее число, которое можно разделить на каждое из чисел от 1 до 10 без остатка. Какое наименьшее положительное число делится на все числа от 1 до 20 без остатка?”

Для решения этой проблемы мы можем использовать различные подходы. Вот несколько методов с примерами кода:

Метод 1: перебор
Мы можем перебрать все числа, начиная с 1, и проверить, делится ли каждое число на все числа от 1 до 20. Как только мы найдем число, удовлетворяющее этому условию, мы вернем его. в результате.

def smallest_divisible_brute_force():
    num = 1
    while True:
        divisible = True
        for i in range(1, 21):
            if num % i != 0:
                divisible = False
                break
        if divisible:
            return num
        num += 1
result = smallest_divisible_brute_force()
print(result)

Метод 2: разложение на простые множители
Мы можем найти разложение на простые множители каждого числа от 1 до 20, а затем умножить высшие степени всех простых множителей. Это даст нам наименьшее число, которое делится на все числа от 1 до 20.

def smallest_divisible_prime_factor():
    primes = [2, 3, 5, 7, 11, 13, 17, 19]
    result = 1
    for prime in primes:
        power = 1
        while prime  power <= 20:
            power += 1
        result *= prime  (power - 1)
    return result
result = smallest_divisible_prime_factor()
print(result)

Метод 3: НОК (наименьшее общее кратное)
Мы можем использовать концепцию наименьшего общего кратного (НОК), чтобы найти наименьшее число, делящееся на все числа от 1 до 20. Мы итеративно вычисляем НОК текущее число и следующее число, пока не достигнем 20.

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def lcm(a, b):
    return a * b // gcd(a, b)
def smallest_divisible_lcm():
    result = 1
    for i in range(1, 21):
        result = lcm(result, i)
    return result
result = smallest_divisible_lcm()
print(result)