Zen of Python

Вопрос подписчика

Задает @StSav012:

«Предлагаю задачку на алгоритм.
Для данных n ∈ ℕ и чётного N ≥ n > 1, N ∈ ℕ, найти чётное ñ, ближайшее к n, являющееся делителем N. Если таких чисел несколько, выбрать наибольшее.Конечно, хочется скорость O(log(n)).

def find_closest_even_divisor(n: int, max_n: int) -> int:
    """
    For given n ∈ ℕ and an even N ≥ n, N ∈ ℕ,
    find an even ñ closest to n so that ñ is a divisor of N.

    If there are several such numbers, pick the largest one.
    """

    if max_n <= 0:
        raise ValueError(f"There are no positive divisors for {max_n}")
    if max_n & 1:
        raise ValueError(f"There are no even divisors for {max_n}, which is odd")

    if n > 0.75 * max_n:
        return max_n

    if max_n % n == 0 and n & 1 == 0:
        return n

    divisors: list[int] = []
    dd: int = 1
    while max_n > 1 and max_n & 1 == 0:
        max_n >>= 1
        dd <<= 1
        divisors.append(dd)

    d: int = 3
    dc: list[int]
    while max_n > 1:
        dc = []
        dd = 1
        while max_n % d == 0:
            max_n //= d
            dd *= d
            dc.append(dd)
        else:
            if dc:
                divisors += [divisor * dd for divisor in divisors for dd in dc]
            if d < isqrt(max_n) and d < 2 * n:
                d += 2
            else:
                break

    return min(divisors, key=lambda _d: (abs(n - _d), -_d))

Что ещё можно ускорить?»

NB! Пожалуйста, будьте взаимовежливы. Однажды и вам помогут в этой рубрике.

#обсуждение
@zen_of_python

✍1

www.tgoop.com/zen_of_python/4494

2.03K viewsSep 10 at 08:06

Вопрос подписчика

Задает @StSav012:

«Предлагаю задачку на алгоритм.
Для данных n ∈ ℕ и чётного N ≥ n > 1, N ∈ ℕ, найти чётное ñ, ближайшее к n, являющееся делителем N. Если таких чисел несколько, выбрать наибольшее.Конечно, хочется скорость O(log(n)).

def find_closest_even_divisor(n: int, max_n: int) -> int:
    """
    For given n ∈ ℕ and an even N ≥ n, N ∈ ℕ,
    find an even ñ closest to n so that ñ is a divisor of N.

    If there are several such numbers, pick the largest one.
    """

    if max_n <= 0:
        raise ValueError(f"There are no positive divisors for {max_n}")
    if max_n & 1:
        raise ValueError(f"There are no even divisors for {max_n}, which is odd")

    if n > 0.75 * max_n:
        return max_n

    if max_n % n == 0 and n & 1 == 0:
        return n

    divisors: list[int] = []
    dd: int = 1
    while max_n > 1 and max_n & 1 == 0:
        max_n >>= 1
        dd <<= 1
        divisors.append(dd)

    d: int = 3
    dc: list[int]
    while max_n > 1:
        dc = []
        dd = 1
        while max_n % d == 0:
            max_n //= d
            dd *= d
            dc.append(dd)
        else:
            if dc:
                divisors += [divisor * dd for divisor in divisors for dd in dc]
            if d < isqrt(max_n) and d < 2 * n:
                d += 2
            else:
                break

    return min(divisors, key=lambda _d: (abs(n - _d), -_d))

BY Zen of Python