素数筛

 埃式筛

import math


def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    p = 2
    while p * p <= n:
        if is_prime[p] == True:
            for i in range(p * p, n + 1, p):
                is_prime[i] = False
        p += 1

    prime_numbers = [p for p in range(2, n + 1) if is_prime[p]]
    return prime_numbers


def lcm_using_log(n):
    primes = sieve_of_eratosthenes(n)
    lcm = 1
    for p in primes:
        max_power = math.floor(math.log(n) / math.log(p))
        lcm *= p ** max_power
    return lcm

1到n的LCM求法：

为 累乘 P ** （log(n) / log(p)）（向下取整）

欧拉筛