Задает @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