Статья Автор: Логинов Даниил

быстрая чудо-программа для поиска наименьшего числа, у которого n делителей

def is_prime(n):
    return all(n % d != 0 for d in range(2, n - 1))


def next_prime(n):
    while not is_prime(n):
        n += 1
    return n


def search(target):
    p = [2]

    def factorizations(limit, n):
        if n == 1:
            yield ()
            return
        for d in range(2, limit + 1)[::-1]:
            if n % d == 0:
                for f in factorizations(d, n // d):
                    yield (d, ) + f

    def candidates():
        nonlocal p
        for f in factorizations(target, target):
            while len(p) < len(f):
                p.append(next_prime(p[-1] + 1))

            r = 1
            for p_i, f_i in zip(p, f):
                r *= p_i ** (f_i - 1)
            yield r

    return min(candidates())


print(search(int(input())))

Чтобы оставить комментарий нужна авторизация

Печать