Find the first integer with exactly $n$ divisors
Some observations: If p is a prime, then $p^{n-1}$ has exactly n divisors. And if for example p, q, r are different primes, then $p^{n-1} q^{m-1} r^{j-1}$ has exactly n * m * j divisors.

And that's the only way we can find numbers with exactly n divisors: We write n as a product n = n1 * n2 * n3 ..., then find primes p1, p2, p3 and so on, and the product $p1^{n1-1} p2^{n2-1} p3^{n3-1} ...$ has exactly n divisors.

If we sort so that n1 ≥ n2 ≥ n3, then a product that is not in the form $2^{n1-1} 3^{n2-1} 5^{n3-1} ... $ can be made smaller while having the same number of divisors by using the primes 2, 3, 5 in that order. For example, if we start with $2^3 5^2$ then $2^3 3^2$ has the same number of divisors, but is smaller. Likewise, $3^3 2^2$ can be replaced with $2^3 3^2$ with the same number of divisors, bit smaller. 

So the smallest number with n divisors has the form $2^{n1-1} 3^{n2-1} 5^{n3-1} ... $ with n1 ≥ n2 ≥ n3 ... and n = n1 * n2 * n3 ...

Now a number like n = 1000, or n = $10^{1000}$, can be written as a product in many ways, so you need to reduce the number of possibilities. You can use an algorithm where you try all possible exponents for 2 that could lead to the smallest number with n divisors, then all possible exponents for 3, and so on.

Let n = p1 * p2 * p3 ... * pk, with primes p1 ≥ p2 ≥ p3 ≥ ... ≥ pk. Whenever we choose an exponent, that exponent is either p - 1 where p is the largest prime not used so far, or it is of the form ab - 1 where b is the smallest prime factor of ab, and ab is greater than that largest prime. (That's quite obvious, right? It's a prime or composite minus 1, and since the exponents are in descending order, its the largest prime minus 1, or greater than that). 

n was the product of k primes. Let P be the k-th prime. If an exponent is of the form ab-1, then P is not a factor of the number. And if we have a factor $p^{ab-1}$, then replacing this with $p^{a-1} P^{b-1}$ gives a number with the same number of factors, but smaller unless $p^a &lt; P$.

This hugely reduces the number of choices. Take n = $2^{1000}$ which is the product of 2,000 primes. The k-th prime is very roughly P ≈ 20,000. 

We saw that the smallest number with n divisors can only have a factor $p^{ab-1}$ if $p^a &lt; P$. We have $2^{15}≥P ≈ 20,000$, $3^{10} ≥ P$, $5^7≥P$, $7^6≥P$, $11^5≥$, and $13^4≥P$, so a ≤ 14 when p = 2, a ≤ 9 when p = 3, a ≤ 6 when P = 5, a ≤ 5 when P = 7, a ≤ 4 when P = 11, and a ≤ 3 when p ≥ 13. And we must have ab ≥ 5, b is the smallest prime factor of ab, and ab must only have prime factors 2 and 5. 

As a result, the only composite exponents minus 1 that are possible in the smallest number with $10^{1000}$ divisors are: $2^{4*2-1}$, $2^{5*2 - 1}$, $2^{5*5 - 1}$, $2^{8*2-1}$, $2^{10*2 - 1}$, $3^{4*2-1}$, $3^{5*2 - 1}$, $3^{5*5 - 1}$, $3^{8*2-1}$, $5^{4*2-1}$, $5^{5*2-1}$, $5^{5*5-1}$, $7^{4*2-1}$, $7^{5*2-1}$, $7^{5*5-1}$, and $11^{4*2-1}$. This is followed by a huge number of factors $p^{5-1}$, finishing with a huge number of factors $p^{2-1}$. 

Since the exponents have to be in non-decreasing order, there is only a small number of cases to try, even for a huge number like $n = 10^{1000}$. 

PS. In your trivial examples, n = 4 = 2 * 2, the solution was $2^{2-1} 3^{2-1} = 6$, and with n = 6 = 3 * 2, the solution was $2^{3-1} 3^{2-1} = 12$. 

PS. Assume you have a more moderately sized n, let's say an n that is the product of 10 primes, making P = 10th prime = 29. We have $2^5&lt;29$, $3^3&lt;29$, $5^2&lt;29$, but $7^2 &gt; 29$. Therefore the only possible factors with an exponent that is not a prime -1 are: $2^{4-1}$, $2^{9-1}$, $2^{6-1}$, $2^{8-1}$, $2^{10-1}$, $2^{25-1}$, $3^{4-1}$, $3^{9-1}$, $3^{6-1}$, and $5^{4-1}$.