x = p1^e1 * p2^e2 * ...,

the number of divisors is (e1+1)*(e2+1)*.... To minimize x for a given divisor-count target, we assign larger exponents to smaller primes (because small primes raised to higher powers grow slower than larger primes).

We implement a constructive search that assigns exponents to the sequence of primes [2,3,5,7,...] with the following rules:

Exponents are non-increasing along the prime list: e1 >= e2 >= e3 .... This ensures we don't waste large exponents on larger primes.
We search over possible exponent combinations using DFS/backtracking, pruning when the partial x exceeds the current best answer or when the product of (ei+1) already reaches N.

This algorithm enumerates exponent tuples in a greedy, ordered manner and finds the minimal x for the required divisor-count.

Method 1 — Constructive search over prime exponents

Intuition

To minimize x for a target divisor-count N, give the largest exponents to the smallest primes. Enforce e1 >= e2 >=

Related Tags

Continue Practicing