Smallest Integer Having At Least N Divisors

Problem

Given an integer N, find the smallest positive integer x such that the number of positive divisors of x is at least N.

Examples

Input: N = 6
Output: 12
Explanation: 12 has 6 divisors (1,2,3,4,6,12) and is the smallest integer with at least 6 divisors.

Input: N = 16
Output: 210
Explanation: 210 = 2*3*5*7 has (1+1)^4 = 16 divisors and is the smallest with ≥16 divisors.

Solution

The brute-force approach (testing every integer and counting its divisors) is too slow for large N. A better strategy is to construct x by assigning exponents to small primes: since

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 >= ... to avoid duplicate permutations of exponents that only reorder primes.

Approach

1. Precompute a list of small primes (first ~15–20 primes) — enough exponents produce large divisor counts.
2. Use DFS with parameters idx (current prime index), prev (maximum exponent allowed for current prime), curr_x (current product), and curr_divs (current product of (ei+1)).
3. At each step, try e from 0 to prev:
   • Update new_x = curr_x * p[idx]^e (stop if this overflows or exceeds best found).
   • Update new_divs = curr_divs * (e+1).
   • If new_divs >= N, update best answer with new_x.
   • Else recurse to idx+1 with prev = e.
4. Prune branches where curr_x already ≥ best answer.

Edge cases: N = 1 -> return 1.

Code

C++

class Solution {
public:
  using u128 = unsigned __int128;
  unsigned long long smallestWithAtLeastNDivs(unsigned long long N) {
    if (N <= 1) return 1ULL;
    vector<unsigned long long> primes = {2,3,5,7,11,13,17,19,23,29,31};
    unsigned long long best = ULLONG_MAX;

    function<void(int,int,u128,unsigned long long)> dfs = [&](int idx, int prev, u128 curr_x, unsigned long long curr_divs){
      if (curr_divs >= N) {
        if (curr_x < best) best = (unsigned long long)curr_x;
        return;
      }
      if (idx >= (int)primes.size()) return;
      for (int e = 0; e <= prev; ++e) {
        // multiply by primes[idx]^e safely
        u128 next_x = curr_x;
        for (int k = 0; k < e; ++k) {
          next_x *= primes[idx];
          if (next_x >= best) break;
        }
        if (next_x >= best) break;
        unsigned long long next_divs = curr_divs * (e + 1ULL);
        dfs(idx + 1, e, next_x, next_divs);
      }
    };

    dfs(0, 64, 1, 1);
    return best;
  }
};

Go

package main

import "math"

var primes = []uint64{2,3,5,7,11,13,17,19,23,29,31}

func smallestWithAtLeastNDivs(N uint64) uint64 {
  if N <= 1 { return 1 }
  best := uint64(math.MaxUint64)

  var dfs func(idx int, prev int, currX uint64, currDivs uint64)
  dfs = func(idx int, prev int, currX uint64, currDivs uint64) {
    if currDivs >= N {
      if currX < best { best = currX }
      return
    }
    if idx >= len(primes) { return }
    for e := 0; e <= prev; e++ {
      nextX := currX
      for k := 0; k < e; k++ {
        if nextX > best/primes[idx] { nextX = best; break }
        nextX *= primes[idx]
      }
      if nextX >= best { break }
      dfs(idx+1, e, nextX, currDivs*uint64(e+1))
    }
  }

  dfs(0, 64, 1, 1)
  return best
}

Java

import java.util.*;

class Solution {
  long[] primes = {2,3,5,7,11,13,17,19,23,29,31};
  public long smallestWithAtLeastNDivs(long N) {
    if (N <= 1) return 1L;
    long best = Long.MAX_VALUE;
    class DF {
      void run(int idx, int prev, java.math.BigInteger currX, long currDivs) {
        if (currDivs >= N) { if (currX.compareTo(java.math.BigInteger.valueOf(best)) < 0) best = currX.longValue(); return; }
        if (idx >= primes.length) return;
        for (int e = 0; e <= prev; ++e) {
          java.math.BigInteger nextX = currX;
          for (int k = 0; k < e; ++k) { nextX = nextX.multiply(java.math.BigInteger.valueOf(primes[idx])); if (nextX.compareTo(java.math.BigInteger.valueOf(best)) >= 0) break; }
          if (nextX.compareTo(java.math.BigInteger.valueOf(best)) >= 0) break;
          run(idx+1, e, nextX, currDivs * (e+1));
        }
      }
    }
    new DF().run(0, 64, java.math.BigInteger.ONE, 1L);
    return best;
  }
}

Kotlin

class Solution {
  private val primes = longArrayOf(2,3,5,7,11,13,17,19,23,29,31)
  fun smallestWithAtLeastNDivs(N: Long): Long {
    if (N <= 1) return 1L
    var best = Long.MAX_VALUE
    fun dfs(idx: Int, prev: Int, currX: java.math.BigInteger, currDivs: Long) {
      if (currDivs >= N) { if (currX < java.math.BigInteger.valueOf(best)) best = currX.toLong(); return }
      if (idx >= primes.size) return
      for (e in 0..prev) {
        var nextX = currX
        for (k in 0 until e) { nextX = nextX.multiply(java.math.BigInteger.valueOf(primes[idx])); if (nextX >= java.math.BigInteger.valueOf(best)) break }
        if (nextX >= java.math.BigInteger.valueOf(best)) break
        dfs(idx+1, e, nextX, currDivs * (e+1))
      }
    }
    dfs(0, 64, java.math.BigInteger.ONE, 1L)
    return best
  }
}

Python

from math import prod
from typing import List

class Solution:
    def smallest_with_at_least_n_divs(self, N: int) -> int:
        if N <= 1: return 1
        primes = [2,3,5,7,11,13,17,19,23,29,31]
        best = 10**30

        def dfs(idx: int, prev: int, curr_x: int, curr_divs: int) -> None:
            nonlocal best
            if curr_divs >= N:
                if curr_x < best: best = curr_x
                return
            if idx >= len(primes): return
            p = primes[idx]
            x = curr_x
            for e in range(0, prev+1):
                if e > 0:
                    x *= p
                    if x >= best: break
                dfs(idx+1, e, x, curr_divs * (e+1))

        dfs(0, 60, 1, 1)
        return best

Rust

pub struct Solution;
impl Solution {
    pub fn smallest_with_at_least_n_divs(n: u64) -> u128 {
        if n <= 1 { return 1 }
        let primes: [u128;11] = [2,3,5,7,11,13,17,19,23,29,31];
        let mut best: u128 = u128::MAX;
        fn dfs(idx: usize, prev: usize, curr_x: u128, curr_divs: u64, n: u64, primes: &[u128], best: &mut u128) {
            if curr_divs >= n { if curr_x < *best { *best = curr_x }; return }
            if idx >= primes.len() { return }
            let p = primes[idx];
            let mut x = curr_x;
            for e in 0..=prev {
                if e > 0 { x = x.saturating_mul(p); if x >= *best { break } }
                dfs(idx+1, e, x, curr_divs * (e as u64 + 1), n, primes, best);
            }
        }
        dfs(0, 60, 1, 1, n, &primes, &mut best);
        best
    }
}

Complexity

• ⏰ Time complexity: highly input-dependent. The DFS enumerates exponent tuples with pruning; in practice for reasonable N (e.g., N up to a few thousand) the search finishes quickly because the exponent-space is small and pruning is effective.
• 🧺 Space complexity: O(k) recursion depth where k is number of primes used (typically 10–15).