Super Ugly Number (Number whose prime factors are in given set)

Namachila October 13, 2025

0 0 11 minutes read

Super ugly numbers are positive numbers whose all prime factors are in the given prime list. Given a number n, the task is to find the nth Super Ugly number.
It may be assumed that a given set of primes is sorted. Also, the first Super Ugly number is 1 by convention.

Examples:

Input  : primes[] = [2, 5]
         n = 5
Output : 8
Super Ugly numbers with given prime factors 
are 1, 2, 4, 5, 8, ...
Fifth Super Ugly number is 8

Input  : primes[] = [2, 3, 5]
         n = 50
Output : 243

Input : primes[] = [3, 5, 7, 11, 13]
        n = 9
Output: 21

In our previous post, we discussed Ugly Number. This problem is basically an extension of Ugly Numbers.
A simple solution for this problem is to one by one pick each number starting from 1 and find it’s all primes factors, if all prime factors lie in the given set of primes that means the number is Super Ugly. Repeat this process until we get nth Super Ugly Number.

An efficient solution for this problem is similar to Method-2 of Ugly Number. Here is the algorithm:

Let k be the size of a given array of prime numbers.
Declare a set for super ugly numbers.
Insert the first ugly number (which is always 1) into the set.
Initialize array multiple_of[k] of size k with 0. Each element of this array is an iterator for the corresponding prime in primes[k] array.
Initialize nextMultipe[k] array with primes[k]. This array behaves like next multiple variables of each prime in given primes[k] array i.e; nextMultiple[i] = primes[i] * ugly[++multiple_of[i]].
Now loop until there are n elements in set ugly.
a). Find minimum among current multiples of primes in nextMultiple[] array and insert it in the set of ugly numbers.
b). Then find this current minimum is multiple of which prime.
c). Increase iterator by 1 i.e; ++multiple_Of[i], for next multiple of current selected prime and update nextMultiple for it.

Below is the implementation of the above steps.

CPP

// C++ program to find n'th Super Ugly number 
#include<bits/stdc++.h> 
using namespace std; 
  
// Function to get the nth super ugly number 
// primes[]       --> given list of primes f size k 
// ugly           --> set which holds all super ugly 
//                    numbers from 1 to n 
// k              --> Size of prime[] 
int superUgly(int n, int primes[], int k) 
{ 
    // nextMultiple holds multiples of given primes 
    vector<int> nextMultiple(primes, primes+k); 
  
    // To store iterators of all primes 
    int multiple_Of[k]; 
    memset(multiple_Of, 0, sizeof(multiple_Of)); 
  
    // Create a set to store super ugly numbers and 
    // store first Super ugly number 
    set<int> ugly; 
    ugly.insert(1); 
  
    // loop until there are total n Super ugly numbers 
    // in set 
    while (ugly.size() != n) 
    { 
        // Find minimum element among all current 
        // multiples of given prime 
        int next_ugly_no = *min_element(nextMultiple.begin(), 
                                    nextMultiple.end()); 
  
        // insert this super ugly number in set 
        ugly.insert(next_ugly_no); 
  
        // loop to find current minimum is multiple 
        // of which prime 
        for (int j=0; j<k; j++) 
        { 
            if (next_ugly_no == nextMultiple[j]) 
            { 
                // increase iterator by one for next multiple 
                // of current prime 
                multiple_Of[j]++; 
  
                // this loop is similar to find  dp[++index[j]] 
                // it -->  dp[++index[j]] 
                set<int>::iterator it = ugly.begin(); 
                for (int i=1; i<=multiple_Of[j]; i++) 
                    it++; 
  
                nextMultiple[j] = primes[j] * (*it); 
                break; 
            } 
        } 
    } 
  
    // n'th super ugly number 
    set<int>::iterator it = ugly.end(); 
    it--; 
    return *it; 
} 
  
/* Driver program to test above functions */
int main() 
{ 
    int primes[] = {2,  5}; 
    int k = sizeof(primes)/sizeof(primes[0]); 
    int n = 5; 
    cout << superUgly(n, primes, k); 
    return 0; 
} 

Java

import java.util.*; 
  
class Main { 
  public static void main(String[] args) 
  { 
    int[] primes = { 2, 5 }; 
    int k = primes.length; 
    int n = 5; 
    System.out.println(superUgly(n, primes, k)); 
  } 
  
  // Function to get the nth super ugly number 
  // primes[]       --> given list of primes f size k 
  // ugly           --> set which holds all super ugly 
  //                    numbers from 1 to n 
  // k              --> Size of prime[] 
  public static int superUgly(int n, int[] primes, int k) 
  { 
    // nextMultiple holds multiples of given primes 
    int[] nextMultiple = Arrays.copyOf(primes, k); 
  
    // To store iterators of all primes 
    int[] multiple_Of = new int[k]; 
    Arrays.fill(multiple_Of, 0); 
  
    // Create a set to store super ugly numbers and 
    // store first Super ugly number 
    Set<Integer> ugly = new HashSet<>(); 
    ugly.add(1); 
  
    // loop until there are total n Super ugly numbers 
    // in set 
    while (ugly.size() != n) { 
      // Find minimum element among all current 
      // multiples of given prime 
      int next_ugly_no = Integer.MAX_VALUE; 
      for (int i = 0; i < k; i++) { 
        next_ugly_no = Math.min(next_ugly_no, 
                                nextMultiple[i]); 
      } 
  
      // insert this super ugly number in set 
      ugly.add(next_ugly_no); 
  
      // loop to find current minimum is multiple 
      // of which prime 
      for (int j = 0; j < k; j++) { 
        if (next_ugly_no == nextMultiple[j]) { 
          // increase iterator by one for next 
          // multiple of current prime 
          multiple_Of[j]++; 
  
          // this loop is similar to find 
          // dp[++index[j]] it -->  dp[++index[j]] 
          List<Integer> uglyList 
            = new ArrayList<>(ugly); 
          int it 
            = uglyList.get(multiple_Of[j] - 1); 
          nextMultiple[j] = primes[j] * it; 
          break; 
        } 
      } 
    } 
  
    // n'th super ugly number 
    List<Integer> uglyList = new ArrayList<>(ugly); 
    return uglyList.get(uglyList.size() - 1); 
  } 
} 
  
// This code is contributed by divyansh2212

Python3

# Python3 program to find n'th Super Ugly number 
from typing import List
  
# Function to get the nth super ugly number 
# primes[]       --> given list of primes f size k 
# ugly           --> set which holds all super ugly 
#                    numbers from 1 to n 
# k              --> Size of prime[] 
def superUgly(n: int, primes: List[int], k: int) -> int: 
    
    # nextMultiple holds multiples of given primes 
    nextMultiple = primes[:] 
  
    # To store iterators of all primes 
    multiple_Of = [0] * k 
  
    # Create a set to store super ugly numbers and 
    # store first Super ugly number 
    ugly = set([1]) 
  
    # loop until there are total n Super ugly numbers 
    # in set 
    while len(ugly) != n: 
        # Find minimum element among all current 
        # multiples of given prime 
        next_ugly_no = min(nextMultiple) 
  
        # insert this super ugly number in set 
        ugly.add(next_ugly_no) 
  
        # loop to find current minimum is multiple 
        # of which prime 
        for j in range(k): 
            if next_ugly_no == nextMultiple[j]: 
                # increase iterator by one for next multiple 
                # of current prime 
                multiple_Of[j] += 1
  
                # this loop is similar to find  dp[++index[j]] 
                # it -->  dp[++index[j]] 
                it = sorted(ugly)[multiple_Of[j]] 
                nextMultiple[j] = primes[j] * it 
                break
  
    # n'th super ugly number 
    return max(ugly) 
  
# Driver program to test above functions  
if __name__ == '__main__': 
    primes = [2,  5] 
    k = len(primes) 
    n = 5
    print(superUgly(n, primes, k)) 
  
    # This code is contributed by lokeshpotta20.

C#

using System; 
using System.Collections.Generic; 
  
class MainClass { 
    public static void Main(string[] args) 
    { 
        int[] primes = { 2, 5 }; 
        int k = primes.Length; 
        int n = 5; 
        Console.WriteLine(superUgly(n, primes, k)); 
    } 
  
    public static int superUgly(int n, int[] primes, int k) 
    { 
        // nextMultiple holds multiples of given primes 
        int[] nextMultiple = new int[k]; 
        Array.Copy(primes, nextMultiple, k); 
  
        // To store iterators of all primes 
        int[] multiple_Of = new int[k]; 
        Array.Fill(multiple_Of, 0); 
  
        // Create a set to store super ugly numbers and 
        // store first Super ugly number 
        HashSet<int> ugly = new HashSet<int>(); 
        ugly.Add(1); 
  
        // loop until there are total n Super ugly numbers 
        // in set 
        while (ugly.Count != n) { 
            // Find minimum element among all current 
            // multiples of given prime 
            int next_ugly_no = Int32.MaxValue; 
            for (int i = 0; i < k; i++) { 
                next_ugly_no = Math.Min(next_ugly_no, 
                                        nextMultiple[i]); 
            } 
  
            // insert this super ugly number in set 
            ugly.Add(next_ugly_no); 
  
            // loop to find current minimum is multiple 
            // of which prime 
            for (int j = 0; j < k; j++) { 
                if (next_ugly_no == nextMultiple[j]) { 
                    // increase iterator by one for next 
                    // multiple of current prime 
                    multiple_Of[j]++; 
  
                    List<int> uglyList 
                        = new List<int>(ugly); 
                    int it = uglyList[multiple_Of[j] - 1]; 
                    nextMultiple[j] = primes[j] * it; 
                    break; 
                } 
            } 
        } 
  
        List<int> finalUglyList = new List<int>(ugly); 
        return finalUglyList[finalUglyList.Count - 1]; 
    } 
}

Javascript

function superUgly(n, primes, k) { 
  // nextMultiple holds multiples of given primes 
  let nextMultiple = primes.slice(); 
  
  // To store iterators of all primes 
  let multipleOf = new Array(k).fill(0); 
  
  // Create a set to store super ugly numbers and 
  // store first Super ugly number 
  let ugly = new Set(); 
  ugly.add(1); 
  
  // loop until there are total n Super ugly numbers 
  // in set 
  while (ugly.size !== n) { 
    // Find minimum element among all current 
    // multiples of given prime 
    let nextUglyNo = Math.min(...nextMultiple); 
  
    // insert this super ugly number in set 
    ugly.add(nextUglyNo); 
  
    // loop to find current minimum is multiple 
    // of which prime 
    for (let j = 0; j < k; j++) { 
      if (nextUglyNo === nextMultiple[j]) { 
        // increase iterator by one for next multiple 
        // of current prime 
        multipleOf[j]++; 
  
        // this loop is similar to find  dp[++index[j]] 
        // it -->  dp[++index[j]] 
        let it = ugly.values(); 
        for (let i = 1; i <= multipleOf[j]; i++) 
          it.next(); 
  
        nextMultiple[j] = primes[j] * it.next().value; 
        break; 
      } 
    } 
  } 
  
  // n'th super ugly number 
  let result = Array.from(ugly).pop(); 
  return result; 
} 
  
// Driver program 
let primes = [2, 5]; 
let k = primes.length; 
let n = 5; 
console.log(superUgly(n, primes, k)); // Output: 8 

Output

This article is contributed by Shashank Mishra .

Another method (using priority_queue)
Here we use min heap priority_queue.
The idea is to push the first ugly no. which is 1 into priority_queue and at every iteration take the top of priority_queue and push all the multiples of that top into priority_queue.
Assuming a[] = {2, 3, 5},
so at first iteration 1 is top so 1 is popped and 1 * 2, 1 * 3, 1 * 5 is pushed.
At second iteration min is 2, so it is popped and 2 * 2, 2 * 3, 2 * 5 is pushed and so on.

Implementation:

CPP

// C++ program for super ugly number 
#include<bits/stdc++.h> 
using namespace std; 
// function will return the nth super ugly number 
int ugly(int a[], int size, int n){ 
      
    // n cannot be negative hence  
    // return -1 if n is 0 or -ve 
    if(n <= 0) 
        return -1; 
   
    if(n == 1) 
        return 1; 
      
    // Declare a min heap priority queue 
    priority_queue<int, vector<int>, greater<int>> pq; 
      
    // Push all the array elements to priority queue 
    for(int i = 0; i < size; i++){ 
        pq.push(a[i]); 
    } 
      
    // once count = n we return no 
    int count = 1, no; 
      
    while(count < n){ 
        // Get the minimum value from priority_queue 
        no = pq.top(); 
        pq.pop(); 
          
        // If top of pq is no then don't increment count. 
        // This to avoid duplicate counting of same no. 
        if(no != pq.top()) 
        { 
            count++; 
          
            // Push all the multiples of no. to priority_queue 
            for(int i = 0; i < size; i++){ 
                pq.push(no * a[i]); 
            // cnt+=1; 
        } 
        } 
    } 
    // Return nth super ugly number 
    return no; 
} 
  
/* Driver program to test above functions */
int main(){ 
    int a[3] = {2, 3,5}; 
    int size = sizeof(a) / sizeof(a[0]); 
    cout << ugly(a, size, 10)<<endl; 
    return 0; 
} 

Java

import java.util.PriorityQueue; 
  
public class SuperUglyNumber { 
  
    // function will return the nth super ugly number 
    public static int ugly(int[] a, int size, int n) { 
  
        // n cannot be negative hence  
        // return -1 if n is 0 or -ve 
        if(n <= 0) 
            return -1; 
  
        if(n == 1) 
            return 1; 
  
        // Declare a min heap priority queue 
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); 
  
        // Push all the array elements to priority queue 
        for(int i = 0; i < size; i++){ 
            pq.add(a[i]); 
        } 
  
        // once count = n we return no 
        int count = 1, no = 0; 
  
        while(count < n){ 
            // Get the minimum value from priority_queue 
            no = pq.poll(); 
  
            // If top of pq is no then don't increment count. 
            // This to avoid duplicate counting of same no. 
            if(no != pq.peek()) 
            { 
                count++; 
  
                // Push all the multiples of no. to priority_queue 
                for(int i = 0; i < size; i++){ 
                    pq.add(no * a[i]); 
                } 
            } 
        } 
        // Return nth super ugly number 
        return no; 
    } 
  
    /* Driver program to test above functions */
    public static void main(String[] args) { 
        int[] a = {2, 3, 5}; 
        int size = a.length; 
        System.out.println(ugly(a, size, 10)); 
    } 
} 

Python3

# Python3 program for super ugly number 
  
# function will return the nth super ugly number 
def ugly(a, size, n): 
  
    # n cannot be negative hence return -1 if n is 0 or -ve 
    if(n <= 0): 
        return -1
    if(n == 1): 
        return 1
  
    # Declare a min heap priority queue 
    pq = [] 
  
    # Push all the array elements to priority queue 
    for i  in range(size): 
        pq.append(a[i]) 
  
    # once count = n we return no 
    count = 1
    no = 0
    pq = sorted(pq) 
  
    while(count < n): 
        # sorted(pq) 
        # Get the minimum value from priority_queue 
        no = pq[0] 
        del pq[0] 
  
  
        # If top of pq is no then don't increment count. 
        # This to avoid duplicate counting of same no. 
        if(no != pq[0]): 
            count += 1
  
            # Push all the multiples of no. to priority_queue 
            for i in range(size): 
                pq.append(no * a[i]) 
            #   cnt+=1 
        pq = sorted(pq) 
    # Return nth super ugly number 
    return no 
  
# /* Driver program to test above functions */ 
if __name__ == '__main__': 
    a = [2, 3,5] 
    size = len(a) 
    print(ugly(a, size, 1000)) 
  
    # This code is contributed by mohit kumar 29.

C#

using System; 
using System.Collections.Generic; 
  
class Program { 
  static int Ugly(int[] a, int size, int n) { 
  
    // n cannot be negative hence return -1 if n is 0 or -ve 
    if(n <= 0) { 
      return -1; 
    } 
    if(n == 1) { 
      return 1; 
    } 
  
    // Declare a min heap priority queue 
    List<int> pq = new List<int>(); 
  
    // Push all the array elements to priority queue 
    for(int i = 0; i < size; i++) { 
      pq.Add(a[i]); 
    } 
  
    // once count = n we return no 
    int count = 1; 
    int no = 0; 
    pq.Sort(); 
  
    while(count < n) { 
      // Get the minimum value from priority_queue 
      no = pq[0]; 
      pq.RemoveAt(0); 
  
      // If top of pq is no then don't increment count. 
      // This to avoid duplicate counting of same no. 
      if(no != pq[0]) { 
        count++; 
  
        // Push all the multiples of no. to priority_queue 
        for(int i = 0; i < size; i++) { 
          pq.Add(no * a[i]); 
        } 
      } 
      pq.Sort(); 
    } 
    // Return nth super ugly number 
    return no; 
  } 
  
  // Driver program to test above functions 
  static void Main() { 
    int[] a = {2, 3, 5}; 
    int size = a.Length; 
    Console.WriteLine(Ugly(a, size, 1000)); 
  } 
} 

Javascript

<script> 
// Javascript program for super ugly number 
      
    //function will return the nth super ugly number 
    function ugly(a,size,n) 
    { 
        //n cannot be negative hence return -1 if n is 0 or -ve 
    if(n <= 0) 
        return -1; 
    
    if(n == 1) 
        return 1; 
       
    // Declare a min heap priority queue 
    let pq=[];; 
       
    // Push all the array elements to priority queue 
    for(let i = 0; i < size; i++){ 
        pq.push(a[i]); 
    } 
       
    // once count = n we return no 
    let count = 1, no; 
    pq.sort(function(a,b){return a-b;}) ; 
      
    while(count < n){ 
        // Get the minimum value from priority_queue 
        no = pq.shift(); 
          
           
        // If top of pq is no then don't increment count. This to avoid duplicate counting of same no. 
        if(no != pq[0]) 
        { 
            count++; 
           
            //Push all the multiples of no. to priority_queue 
            for(let i = 0; i < size; i++){ 
                pq.push(no * a[i]); 
            //    cnt+=1; 
        } 
          
        } 
        pq.sort(function(a,b){return a-b;}) ; 
    } 
    // Return nth super ugly number 
    return no; 
    } 
      
      
    /* Driver program to test above functions */
    let a=[2, 3,5]; 
    let size = a.length; 
    document.write(ugly(a, size, 1000)); 
      
      
    // This code is contributed by unknown2108 
</script>

Output

Time Complexity: O(n*size*logn)
Auxiliary Space: O(n)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above. If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!