Algorithm for finding smallest number with given number of factors

Question

What's the most efficient algorithm anyone can think of that, given a natural number n, returns the least natural number x with n positive divisors (including 1 and x)? For example, given 4 the algorithm should result in 6 (divisors: 1,2,3,6); i.e. 6 is the smallest number having 4 distinct factors. Similarly, given 6, the algorithm should result in 12 (divisors: 1,2,3,4,6,12); i.e. 12 is the smallest number having 6 distinct factors

In terms of real-world performance, I'm looking for a scalable algorithm which can give answers of the order of 10²⁰ within 2 seconds on a machine which can do 10⁷ computations per second.

Answer 1

http://www.primepuzzles.net/problems/prob_019.htm

b) Jud McCranie, T.W.A. Baumann & Enoch Haga sent basically the same procedure to find N(d) for a given d:

1. Factorize d as a product of his prime divisors: d = p₁^a₁ * p₂^a₂ *p₃^a₃ *...
2. convert this factorization in another arithmetically equivalent factorization, composed of non-powered monotonically decreasing and not necesarilly prime factors... (uf!...) d = p₁^a₁ * p₂^a₂ *p₃^a₃ *... = b₁ * b₂ * b₃... such that b₁ ≥ b₂ ≥ b₃...
   You must realize that for every given d, there are several arithmetically equivalent factorizations that can be done: by example:
   if d = 16 = 2⁴ then there are 5 equivalent factorizations: d = 2*2*2*2 = 4*2*2 = 4*4 = 8*2 = 16
3. N is the minimal number resulting of computing 2^b₁-1 * 3^b₂-1 * 5^b₃-1 * ... for all the equivalent factorizations of d. Working the same example:
   N(16) = the minimal of these {2 * 3 * 5 * 7, 2³ * 3 * 5, 2³ * 3³, 2⁷ * 3, 2¹⁵} = 2³ * 3 * 5 = 120

Update: With numbers around 10²⁰, pay attention to the notes by Christian Bau quoted on the same page.