Great question! Let's break this down clearly, covering both prime and composite values of n—since we need a unified approach. First, let's recap the core math behind divisor counts, as this is the foundation for everything:

For any positive integer ( N ) with prime factorization ( N = p_1^{a_1} \times p_2^{a_2} \times ... \times p_k^{a_k} ), the number of positive divisors of ( N ) is given by:
( d(N) = (a_1 + 1)(a_2 + 1)...(a_k + 1) )

Our goal is to find the i-th smallest ( N ) where ( d(N) = n ), regardless of whether n is prime or composite.

Step 1: Enumerate Valid Exponent Combinations #

First, we need to find all non-increasing sequences of positive integers ( (a_1, a_2, ..., a_k) ) such that the product of ( (a_i + 1) ) equals n. This ensures we cover all possible ways to get exactly n divisors, without redundant combinations.

Examples: #

• If n is prime (say n=5):
  The only way to write 5 as a product of integers >1 is ( 5 = 5 ), so the only exponent sequence is ( (4) ) (since ( 4 + 1 = 5 )).
• If n is composite (say n=6):
  We can write 6 as ( 6 = 6 ) or ( 6 = 3 \times 2 ). Converting these to exponent sequences (subtract 1 from each factor, then sort in non-increasing order):
  • ( 6-1 = 5 ) → sequence ( (5) )
  • ( 3-1=2, 2-1=1 ) → sorted to ( (2, 1) )

Step 2: Generate Candidate Numbers Efficiently #

Instead of brute-forcing every integer (which is slow for large i or n), we use a min-heap (priority queue) to generate candidates in sorted order. Here's how:

1. Precompute a list of primes: Use the Sieve of Eratosthenes to generate enough primes (e.g., the first 100 primes—this covers most practical cases).
2. Initialize the heap:
   • For each valid exponent sequence ( (a_1, a_2, ..., a_k) ):
     • Take the first k primes from your list (e.g., 2, 3, 5 for k=3)
     • Compute the candidate number ( N = 2^{a_1} \times 3^{a_2} \times ... \times p_k^{a_k} )
     • Add this candidate to the heap, along with metadata: the exponent sequence, and the indices of the primes used (to avoid duplicates later)
3. Extract and generate candidates until we reach the i-th number:
   • Repeat the following steps:
     a. Pop the smallest number from the heap—this is the m-th valid number (start m at 1).
     b. If m == i, return this number as your answer.
     c. Generate new candidates from the popped number:
     • For the corresponding exponent sequence and prime indices ( (idx_1, idx_2, ..., idx_k) ):
       • For each position j (from 1 to k), replace the j-th prime with the next larger prime (i.e., idx_j + 1), as long as the new prime is larger than the previous one (to maintain increasing primes and avoid duplicate candidates).
       • Compute the new candidate number and add it to the heap only if it hasn't been added before (use a set to track seen candidates to avoid duplicates).

Example Walkthrough: Find the 3rd number with 6 divisors #

1. Valid exponent sequences: ( (5) ) and ( (2, 1) )
2. Initialize heap with:
   • ( 2^5 = 32 ) (from sequence (5))
   • ( 2^2 \times 3^1 = 12 ) (from sequence (2,1))
3. Process the heap:
   • Pop 12 (1st number). Generate new candidates: ( 2^2 \times 5^1 = 20 ) and ( 3^2 \times 2^1 = 18 ). Add both to the heap.
   • Pop 18 (2nd number). Generate new candidate: ( 3^2 \times 5^1 = 45 ). Add to heap.
   • Pop 20 (3rd number). Since we need the 3rd number, return 20.

Special Case: n is Prime #

When n is a prime number p, the only valid exponent sequence is ( (p-1) ) (since ( (p-1)+1 = p = n )). This means all valid numbers are primes raised to the power of ( p-1 ), sorted in ascending order.

Example: n=3 (prime) #

• Valid numbers are ( 2^2=4 ), ( 3^2=9 ), ( 5^2=25 ), ( 7^2=49 ), etc.
• The 2nd number is 9.

Key Optimizations #

• Non-increasing exponent sequences: Prevents generating redundant candidates (e.g., we don't need both ( (1,2) ) and ( (2,1) ) since they produce the same set of numbers, just reordered).
• Min-heap for sorted candidates: Ensures we always get the next smallest number without checking every integer.
• Track seen candidates: Avoids adding duplicate values to the heap, saving time and memory.

内容的提问来源于stack exchange，提问作者Chyle Andrei Lee