Получается вот что. Поскольку теория чисел говорит нам, что число, которое разлагается на простые множители в виде 2^p*3^q*5^r..., имеет число делителей

num_divisors = (p+1)*(q+1)*(r+1)*...

то мы можем разложить число num_divisors=5000 = 2*2*2*5*5*5*5 на множители всем возможными способами (их немало, но обозримое количество), и для каждого разложения посчитать результат:

primes = [2,3,5,7,11,13,17]
minn = -1

def fmx(lst):
    num = 1
    global minn
    for i, p in enumerate(lst):
        num *= primes[i]**(p-1)
    if minn == -1:
        minn = num
    else:
        minn = min(num, minn)


def f5000(lst=[], p2=3, p5=4):
    if p2+p5==0:
        fmx(lst)
        return
    for i in range(p2+1):
        for j in range(p5+1):
            if i+j:
                f5000(lst + [2**i * 5**j], p2-i, p5-j)


f5000()

print(minn)

Результат

>>> 4727833110000
2^4 * 3^4 * 5^4 * 7^4 * 11 * 13 * 17

Если вы ищете минимальное число, у которого ровно 5000 делителей, то посмотрите соседний ответ. Или посмотрите раздел = 5000 ниже в этом ответе. А пока

≥ 5000

В статье Сверхсоставное число описаны числа, которые имеют число делителей, большее чем у любого предыдущего. Наша задача – найти первое сверхсоставное число с количеством делителей больше заданного порога.

Сверхсоставные числа имеют вид
∏_i p_i^c_i, где
p_i – последовательные простые числа,
c_i – невозрастающая последовательность степеней.

Произведение конечно, так как начиная с некоторого i c_i становится равным нулю.

Число делителей равно d(∏_i p_i^c_i) = ∏_i (c_i + 1). (статья Функция делителей).

Наша задача перебрать все невозрастающие последовательности c_i, у которых ∏_i (c_i + 1) больше заданного порога, и выбрать из них одну с минимальным ∏_i p_i^c_i.

Ещё понадобится свойство монотонности: если в c_i увеличить любой элемент на единицу, увеличатся и произведение и число делителей. Всё, этого достаточно чтобы написать код.

is_prime и next_prime отыскивают последовательные простые. Прошу прощения за их медлительность. В нашей задаче большие простые числа не понадобятся, а так код проще.

search отыскивает минимальное сверхсоставное число с нужным количеством делителей. Поиск рекурсивный. Поддерживается последовательность степеней c, количество делителей n_divs и само число-кандидат product. least_product хранит минимального кандидата, что ускоряет поиск (выше было про монотонность).

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):
    least_product = float('inf')
    p = [1]
    c = [target - 1]

    def search(i, n_divs, product):
        nonlocal least_product
        if i >= len(p):
            p.append(next_prime(p[-1] + 1))
            c.append(0)

        if product >= least_product:
            return

        if n_divs >= target:
            if product < least_product:
               least_product = product

        if c[i] > 0:
            search(i + 1, n_divs, product)
        if c[i - 1] > c[i]:
            c[i] += 1
            search(i, n_divs // c[i] * (c[i] + 1), product * p[i])
            c[i] -= 1

    search(1, 1, 1)
    return least_product


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

Почти мгновенно можно отыскать ответ для пяти тысяч и восемь секунд нужно для миллиарда:

$ time echo 5000 | python highly-composite-number.py 
293318625600

real  0m0.036s
user  0m0.024s
sys   0m0.008s

$ time echo 1000000000 | python highly-composite-number.py 
474386058264023040500951689662949694304000

real  0m8.062s
user  0m8.056s
sys   0m0.004s

Поиск устроен так чтобы быстро построить праймориал с нужным количеством делителей. Сам он обычно не является минимальным ответом, но даёт хорошее ограничение сверху. Для 5000 это:

304250263527210 = 2·3·5·7·11·13·17·19·23·29·31·37·41

У него 8192 (= 2¹³) делителей, а вектор степеней c_i состоит из триннадцати единиц.

Это не лучшее решение. Чтобы отыскать минимум, поиск проверяет ещё около девяти тысяч векторов. Вот некоторые, в порядке улучшения разультата:

= 5000

Чтобы перебрать все числа, имеющие ровно 5000 делителей, нужно разложить 5000 во всевозможные произведения и для каждого произведения составить число с пятью тысячами делителей. Например:

Любое число вида p_i⁶²⁴p_j⁷, где pi и pj различные простые, будет иметь ровно 5000 делителей. Рецепт прост: различные простые возводятся в степени на единицу меньшие множителей из разложения.

Так как мы ищем минимальные кандидаты, то простые будем брать из начала ряда и расположим множители по убыванию. Всего у пяти тысяч – 57 разложений.

Код не очень эффективный, зато простой:

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())))

Для 5000 считает мгновенно. Для миллиарда надо подождать три минуты:

$ time echo 5000 | python highly-composite-number.py
4727833110000

real  0m0.030s
user  0m0.024s
sys   0m0.004s

$ time echo 1000000000 | python highly-composite-number.py
683175381189232829757128698827279802247046720000

real  2m39.379s
user  2m38.400s
sys   0m0.804s