Data Modelling & AI Data Structure & Algorithm

Check if a number exists having exactly N factors and K prime factors

23 June 2025

0

Given two numbers N and K, the task is to find whether an integer X exists such that it has exactly N factors and K out of them are prime.
Examples:

Input: N = 4, K = 2
Output: Yes
Explanation:
One possible number for X is 6.
The number 6 has a total 4 factors: 1, 2, 3 & 6.
It also has exactly 2 prime factors: 2 & 3.
Input: N = 3, K = 1
Output: Yes
Explanation:
One possible number for X is 49.
The number 49 has a total 3 factors: 1, 7, & 49.
It also has exactly 1 prime factor: 7.

Approach: The idea is to use the following identity.

For any number X, if the number has N factors out of which K are prime:

X = k1^a + k2^b + k3^c + ... + knⁿ

The total number of factors N is equal to:

N = (a + 1) * (b + 1) * (c + 1) .. (n + 1)

Therefore, the idea is to check if N can be represented as a product of K integers greater than 1. This can be done by finding the divisors of the number N.
If the count of this is less than K, then the answer is not possible. Else, it is possible.

Below is the implementation of the above approach:

C++

// C++ program to check if it
// is possible to make a number
// having total N factors and
// K prime factors
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to compute the
// number of factors of
// the given number
bool factors(int n, int k)
{
    // Vector to store
    // the prime factors
    vector<int> v;
 
    // While there are no
    // two multiples in
    // the number, divide
    // it by 2
    while (n % 2 == 0) {
        v.push_back(2);
        n /= 2;
    }
 
    // If the size is already
    // greater than K,
    // then return true
    if (v.size() >= k)
        return true;
 
    // Computing the remaining
    // divisors of the number
    for (int i = 3; i * i <= n;
         i += 2) {
 
        // If n is divisible by i,
        // then it is a divisor
        while (n % i == 0) {
            n = n / i;
            v.push_back(i);
        }
 
        // If the size is already
        // greater than K, then
        // return true
        if (v.size() >= k)
            return true;
    }
 
    if (n > 2)
        v.push_back(n);
 
    // If the size is already
    // greater than K,
    // then return true
    if (v.size() >= k)
        return true;
 
    // If none of the above
    // conditions satisfies,
    // then return false
    return false;
}
 
// Function to check if it is
// possible to make a number
// having total N factors and
// K prime factors
void operation(int n, int k)
{
    bool answered = false;
 
    // If total divisors are
    // less than the number
    // of prime divisors,
    // then print No
    if (n < k) {
        answered = true;
        cout << "No"
             << "\n";
    }
 
    // Find the number of
    // factors of n
    bool ok = factors(n, k);
 
    if (!ok && !answered) {
        answered = true;
        cout << "No"
             << "\n";
    }
 
    if (ok && !answered)
        cout << "Yes"
             << "\n";
}
 
// Driver Code
int main()
{
    int n = 4;
    int k = 2;
 
    operation(n, k);
    return 0;
}

Java

// Java program to check if it
// is possible to make a number
// having total N factors and
// K prime factors
import java.io.*; 
import java.util.*;
 
class GFG{ 
     
// Function to compute the
// number of factors of
// the given number
static boolean factors(int n, int k)
{
     
    // Vector to store
    // the prime factors
    ArrayList<Integer> v = new ArrayList<Integer>();
 
    // While there are no
    // two multiples in
    // the number, divide
    // it by 2
    while (n % 2 == 0)
    {
        v.add(2);
        n /= 2;
    }
 
    // If the size is already
    // greater than K,
    // then return true
    if (v.size() >= k)
        return true;
 
    // Computing the remaining
    // divisors of the number
    for(int i = 3; i * i <= n; i += 2)
    {
        
       // If n is divisible by i,
       // then it is a divisor
       while (n % i == 0)
       {
           n = n / i;
           v.add(i);
       }
        
       // If the size is already
       // greater than K, then
       // return true
       if (v.size() >= k)
           return true;
    }
 
    if (n > 2)
        v.add(n);
 
    // If the size is already
    // greater than K,
    // then return true
    if (v.size() >= k)
        return true;
 
    // If none of the above
    // conditions satisfies,
    // then return false
    return false;
}
     
// Function to check if it is
// possible to make a number
// having total N factors and
// K prime factors
static void operation(int n, int k)
{ 
    boolean answered = false;
 
    // If total divisors are
    // less than the number
    // of prime divisors,
    // then print No
    if (n < k)
    {
        answered = true;
        System.out.println("No");
    }
 
    // Find the number of
    // factors of n
    boolean ok = factors(n, k);
 
    if (!ok && !answered) 
    {
        answered = true;
        System.out.println("No");
    }
    if (ok && !answered)
        System.out.println("Yes");
}
     
// Driver code 
public static void main(String[] args) 
{ 
    int n = 4;
    int k = 2;
     
    //Function call
    operation(n, k);
} 
} 
 
// This code is contributed by coder001

Python3

# Python3 program to check if it 
# is possible to make a number 
# having total N factors and 
# K prime factors 
 
# Function to compute the 
# number of factors of 
# the given number 
def factors(n, k):
 
    # Vector to store 
    # the prime factors 
    v = []; 
 
    # While there are no 
    # two multiples in 
    # the number, divide 
    # it by 2 
    while (n % 2 == 0):
        v.append(2); 
        n //= 2; 
     
    # If the size is already 
    # greater than K, 
    # then return true 
    if (len(v) >= k): 
        return True; 
 
    # Computing the remaining 
    # divisors of the number 
    for i in range(3, int(n ** (1 / 2)), 2):
 
        # If n is divisible by i, 
        # then it is a divisor 
        while (n % i == 0):
            n = n // i; 
            v.append(i); 
 
        # If the size is already 
        # greater than K, then 
        # return true 
        if (len(v) >= k):
            return True; 
     
    if (n > 2):
        v.append(n); 
 
    # If the size is already 
    # greater than K, 
    # then return true 
    if (len(v) >= k):
        return True; 
 
    # If none of the above 
    # conditions satisfies, 
    # then return false 
    return False; 
 
# Function to check if it is 
# possible to make a number 
# having total N factors and 
# K prime factors 
def operation(n, k): 
    answered = False; 
 
    # If total divisors are 
    # less than the number 
    # of prime divisors, 
    # then print No 
    if (n < k):
        answered = True; 
        print("No");
 
    # Find the number of 
    # factors of n 
    ok = factors(n, k); 
 
    if (not ok and not answered):
        answered = True; 
        print("No");
 
    if (ok and not answered):
        print("Yes");
 
# Driver Code 
if __name__ == "__main__": 
 
    n = 4;
    k = 2;
    operation(n, k); 
 
# This code is contributed by AnkitRai01

C#

// C# program to check if it 
// is possible to make a number 
// having total N factors and 
// K prime factors 
using System; 
using System.Collections.Generic; 
 
class GFG{ 
     
// Function to compute the 
// number of factors of 
// the given number 
static bool factors(int n, int k) 
{ 
     
    // Vector to store 
    // the prime factors 
    List<int> v = new List<int>(); 
 
    // While there are no 
    // two multiples in 
    // the number, divide 
    // it by 2 
    while (n % 2 == 0) 
    { 
        v.Add(2); 
        n /= 2; 
    } 
 
    // If the size is already 
    // greater than K, 
    // then return true 
    if (v.Count >= k) 
        return true; 
 
    // Computing the remaining 
    // divisors of the number 
    for(int i = 3; i * i <= n; i += 2) 
    { 
         
        // If n is divisible by i, 
        // then it is a divisor 
        while (n % i == 0) 
        { 
            n = n / i; 
            v.Add(i); 
        } 
             
        // If the size is already 
        // greater than K, then 
        // return true 
        if (v.Count >= k) 
            return true; 
    } 
 
    if (n > 2) 
        v.Add(n); 
 
    // If the size is already 
    // greater than K, 
    // then return true 
    if (v.Count >= k) 
        return true; 
 
    // If none of the above 
    // conditions satisfies, 
    // then return false 
    return false; 
} 
     
// Function to check if it is 
// possible to make a number 
// having total N factors and 
// K prime factors 
static void operation(int n, int k) 
{ 
    bool answered = false; 
 
    // If total divisors are 
    // less than the number 
    // of prime divisors, 
    // then print No 
    if (n < k) 
    { 
        answered = true; 
        Console.WriteLine("No"); 
    } 
 
    // Find the number of 
    // factors of n 
    bool ok = factors(n, k); 
 
    if (!ok && !answered) 
    { 
        answered = true; 
        Console.WriteLine("No"); 
    } 
    if (ok && !answered) 
        Console.WriteLine("Yes"); 
} 
     
// Driver code 
public static void Main() 
{ 
    int n = 4; 
    int k = 2; 
     
    // Function call 
    operation(n, k); 
} 
}
 
// This code is contributed by sanjoy_62

Javascript

<script>
 
// Javascript program to check if it
// is possible to make a number
// having total N factors and
// K prime factors
 
// Function to compute the
// number of factors of
// the given number
function factors(n, k)
{
    // Vector to store
    // the prime factors
    let v = [];
 
    // While there are no
    // two multiples in
    // the number, divide
    // it by 2
    while (n % 2 == 0) {
        v.push(2);
        n = parseInt(n/2);
    }
 
    // If the size is already
    // greater than K,
    // then return true
    if (v.length >= k)
        return true;
 
    // Computing the remaining
    // divisors of the number
    for (let i = 3; i * i <= n;
         i += 2) {
 
        // If n is divisible by i,
        // then it is a divisor
        while (n % i == 0) {
            n = parseInt(n / i);
            v.push(i);
        }
 
        // If the size is already
        // greater than K, then
        // return true
        if (v.length >= k)
            return true;
    }
 
    if (n > 2)
        v.push(n);
 
    // If the size is already
    // greater than K,
    // then return true
    if (v.length >= k)
        return true;
 
    // If none of the above
    // conditions satisfies,
    // then return false
    return false;
}
 
// Function to check if it is
// possible to make a number
// having total N factors and
// K prime factors
function operation(n, k)
{
    let answered = false;
 
    // If total divisors are
    // less than the number
    // of prime divisors,
    // then print No
    if (n < k) {
        answered = true;
        document.write("No<br>");
    }
 
    // Find the number of
    // factors of n
    let ok = factors(n, k);
 
    if (!ok && !answered) {
        answered = true;
        document.write("No<br>");
    }
 
    if (ok && !answered)
        document.write("Yes<br>");
}
 
// Driver Code
let n = 4;
let k = 2;
 
operation(n, k);
 
</script>

Output

Yes

Time Complexity: O(n^1/2)

Auxiliary Space: O(n^1/2)

Approach: “Factorization Approach”

Here are the steps involved in the Factorization Approach for checking if there exists an integer X such that it has exactly N factors and K out of them are prime:

Generate prime numbers up to a certain limit. This can be done by iterating over all numbers up to the limit and checking if they are prime using a primality test like trial division or the Sieve of Eratosthenes.
Given a number X, calculate its prime factors using a factorization algorithm like trial division or Pollard’s rho algorithm.
Use the prime factors of X to calculate all possible factors of X. This can be done by generating all possible combinations of the prime factors and multiplying them together to get a factor of X.
Check if the number of factors of X is equal to N and the number of prime factors among the factors is equal to K. If so, return “True” as such a number X exists. If not, continue to the next number and repeat the above steps.
If no such number X is found after checking all numbers up to N, return “False”.

C++

// C++ program for the above approach
#include <algorithm>
#include <cmath>
#include <iostream>
#include <set>
#include <vector>
 
using namespace std;
 
// Function to find the prime factors of
// the number n
vector<int> prime_factors(int n)
{
    // Returns all prime factors of
    // a given number
    vector<int> factors;
    int d = 2;
 
    while (d * d <= n) {
        while (n % d == 0) {
            factors.push_back(d);
            n /= d;
        }
        d += 1;
    }
    if (n > 1) {
        factors.push_back(n);
    }
    return factors;
}
 
// Function to find the prime number
// till limit
vector<int> generate_primes(int limit)
{
    // Stores all prime numbers up
    // to a given limit
    vector<int> primes;
 
    for (int n = 2; n <= limit; n++) {
        if (all_of(primes.begin(), primes.end(),
                   [n](int i) { return n % i != 0; })) {
            primes.push_back(n);
        }
    }
    return primes;
}
 
// Function to find the factors of number n
set<int> calculate_factors(int n, vector<int>& primes)
{
    // Calculates all factors of a number
    // given its prime factors
    set<int> factors = { 1, n };
 
    for (int i = 1; i < primes.size(); i++) {
        for (auto j : vector<vector<int> >(
                 i, vector<int>(primes.size()))) {
            for (int k = 0; k < i; k++) {
                j[k] = 1;
            }
            do {
                int factor = 1;
                for (int p = 0; p < i; p++) {
                    factor *= primes[j[p]];
                }
                factors.insert(factor);
                factors.insert(n / factor);
            } while (next_permutation(j.begin(), j.end()));
        }
    }
    return factors;
}
 
bool check_if_x_exists(int n, int k)
{
    // Checks if there exists an integer X
    // such that it has exactly N factors
    // and K out of them are prime
    vector<int> primes = generate_primes(n);
 
    for (int x = 2; x <= n; x++) {
 
        // Find factors
        set<int> factors = calculate_factors(x, primes);
        int num_primes = count_if(
            factors.begin(), factors.end(),
            [&primes](int f) {
                return find(primes.begin(), primes.end(), f)
                       != primes.end();
            });
        if (factors.size() == n && num_primes == k) {
            return true;
        }
    }
    return false;
}
 
// Driver Code
int main()
{
    cout << check_if_x_exists(4, 2);
 
    return 0;
}

Python3

import itertools
 
def prime_factors(n):
    """ Returns all prime factors of a given number """
    factors = []
    d = 2
    while d * d <= n:
        while (n % d) == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors
 
def generate_primes(limit):
    """ Returns all prime numbers up to a given limit """
    primes = []
    for n in range(2, limit + 1):
        if all(n % i != 0 for i in range(2, int(n ** 0.5) + 1)):
            primes.append(n)
    return primes
 
def calculate_factors(n, primes):
    """ Calculates all factors of a number given its prime factors """
    factors = set([1, n])
    for i in range(1, len(primes)):
        for j in itertools.combinations(primes, i):
            factor = 1
            for p in j:
                factor *= p
            factors.add(factor)
            factors.add(n // factor)
    return sorted(factors)
 
def check_if_x_exists(n, k):
    """ Checks if there exists an integer X such that it has exactly N factors and K out of them are prime """
    primes = generate_primes(n)
    for x in range(2, n + 1):
        factors = calculate_factors(x, primes)
        num_primes = sum(1 for f in factors if f in primes)
        if len(factors) == n and num_primes == k:
            return True
    return False
 
print(check_if_x_exists(4, 2))  # Output: True

C#

using System;
using System.Collections.Generic;
using System.Linq;
 
class Program
{
    static List<int> PrimeFactors(int n)
    {
        // Returns all prime factors of a given number
        List<int> factors = new List<int>();
        int d = 2;
        while (d * d <= n)
        {
            while (n % d == 0)
            {
                factors.Add(d);
                n /= d;
            }
            d += 1;
        }
        if (n > 1)
        {
            factors.Add(n);
        }
        return factors;
    }
 
    static List<int> GeneratePrimes(int limit)
    {
        // Returns all prime numbers up to a given limit
        List<int> primes = new List<int>();
        for (int n = 2; n <= limit; n++)
        {
            if (Enumerable.Range(2, (int)Math.Sqrt(n) - 1).All(i => n % i != 0))
            {
                primes.Add(n);
            }
        }
        return primes;
    }
 
    static List<int> CalculateFactors(int n, List<int> primes)
    {
        // Calculates all factors of a number given its prime factors
        HashSet<int> factors = new HashSet<int> { 1, n };
        for (int i = 1; i < primes.Count(); i++)
        {
            foreach (var combination in Combinations(primes, i))
            {
                int factor = 1;
                foreach (var p in combination)
                {
                    factor *= p;
                }
                factors.Add(factor);
                factors.Add(n / factor);
            }
        }
        return factors.OrderBy(x => x).ToList();
    }
 
    static bool CheckIfXExists(int n, int k)
    {
        // Checks if there exists an integer X such that it has exactly N factors and K out of them are prime
        List<int> primes = GeneratePrimes(n);
        for (int x = 2; x <= n; x++)
        {
            List<int> factors = CalculateFactors(x, primes);
            int numPrimes = factors.Count(f => primes.Contains(f));
            if (factors.Count == n && numPrimes == k)
            {
                return true;
            }
        }
        return false;
    }
 
    static IEnumerable<IEnumerable<T>> Combinations<T>(IEnumerable<T> elements, int k)
    {
        // Returns all combinations of k elements from the given list
        if (k == 0)
        {
            return new List<T>[] { new List<T>() };
        }
        else
        {
            return elements.SelectMany((e, i) =>
                Combinations(elements.Skip(i + 1), k - 1).Select(c => (new T[] { e }).Concat(c)));
        }
    }
 
    static void Main(string[] args)
    {
        Console.WriteLine(CheckIfXExists(4, 2));  // Output: True
    }
}

Javascript

function primeFactors(n) 
{
 
  // Returns all prime factors of a given number
  let factors = [];
  let d = 2;
  while (d * d <= n) {
    while (n % d == 0) {
      factors.push(d);
      n /= d;
    }
    d += 1;
  }
  if (n > 1) {
    factors.push(n);
  }
  return factors;
}
 
function generatePrimes(limit) {
  // Returns all prime numbers up to a given limit
  let primes = [];
  for (let n = 2; n <= limit; n++) {
    let isPrime = true;
    for (let i = 2; i <= Math.sqrt(n); i++) {
      if (n % i == 0) {
        isPrime = false;
        break;
      }
    }
    if (isPrime) {
      primes.push(n);
    }
  }
  return primes;
}
 
function calculateFactors(n, primes) {
  // Calculates all factors of a number given its prime factors
  let factors = new Set([1, n]);
  for (let i = 1; i < primes.length; i++) {
    for (let j of combinations(primes, i)) {
      let factor = 1;
      for (let p of j) {
        factor *= p;
      }
      factors.add(factor);
      factors.add(n / factor);
    }
  }
  return Array.from(factors).sort((a, b) => a - b);
}
 
function checkIfXExists(n, k)
{
  // Checks if there exists an integer X such 
  // that it has exactly N factors and K out of them are prime
  let primes = generatePrimes(n);
  for (let x = 2; x <= n; x++) {
    let factors = calculateFactors(x, primes);
    let numPrimes = factors.filter(f => primes.includes(f)).length;
    if (factors.length == n && numPrimes == k) {
      return true;
    }
  }
  return false;
}
 
function* combinations(iterable, r) 
{
 
  // Returns all combinations of length r from iterable
  let pool = Array.from(iterable);
  let n = pool.length;
  if (r > n) {
    return;
  }
  let indices = Array.from(Array(r).keys());
  yield indices.map(i => pool[i]);
  while (true) {
    let i;
    for (i = r - 1; i >= 0; i--) {
      if (indices[i] != i + n - r) {
        break;
      }
    }
    if (i < 0) {
      return;
    }
    indices[i] += 1;
    for (let j = i + 1; j < r; j++) {
      indices[j] = indices[j - 1] + 1;
    }
    yield indices.map(i => pool[i]);
  }
}
 
console.log(checkIfXExists(4, 2));  // Output: true

Java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
 
public class Main {
    public static List<Integer> primeFactors(int n)
    {
        // Returns all prime factors of a given number
        List<Integer> factors = new ArrayList<Integer>();
        int d = 2;
        while (d * d <= n) {
            while (n % d == 0) {
                factors.add(d);
                n /= d;
            }
            d += 1;
        }
        if (n > 1) {
            factors.add(n);
        }
        return factors;
    }
 
    public static List<Integer> generatePrimes(int limit)
    {
        // Returns all prime numbers up to a given limit
        List<Integer> primes = new ArrayList<Integer>();
        for (int n = 2; n <= limit; n++) {
            boolean isPrime = true;
            for (int i = 2; i <= Math.sqrt(n); i++) {
                if (n % i == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                primes.add(n);
            }
        }
        return primes;
    }
 
    public static Set<Integer>
    calculateFactors(int n, List<Integer> primes)
    {
        // Calculates all factors of a number given its
        // prime factors
        Set<Integer> factors = new HashSet<Integer>();
        factors.add(1);
        factors.add(n);
        for (int i = 1; i < primes.size(); i++) {
            List<List<Integer> > combinations
                = combinations(primes, i);
            for (List<Integer> comb : combinations) {
                int factor = 1;
                for (int p : comb) {
                    factor *= p;
                }
                factors.add(factor);
                factors.add(n / factor);
            }
        }
        return factors;
    }
 
    public static boolean checkIfXExists(int n, int k)
    {
        // Checks if there exists an integer X such that it
        // has exactly N factors and K out of them are prime
        List<Integer> primes = generatePrimes(n);
        for (int x = 2; x <= n; x++) {
            Set<Integer> factors
                = calculateFactors(x, primes);
            int numPrimes = 0;
            for (int f : factors) {
                if (primes.contains(f)) {
                    numPrimes++;
                }
            }
            if (factors.size() == n && numPrimes == k) {
                return true;
            }
        }
        return false;
    }
 
    public static List<List<Integer> >
    combinations(List<Integer> list, int size)
    {
        // Returns all combinations of size "size" from the
        // list "list"
        List<List<Integer> > result
            = new ArrayList<List<Integer> >();
        if (size == 0) {
            result.add(new ArrayList<Integer>());
            return result;
        }
        for (int i = 0; i < list.size(); i++) {
            int head = list.get(i);
            List<Integer> rest = new ArrayList<Integer>(
                list.subList(i + 1, list.size()));
            for (List<Integer> comb :
                 combinations(rest, size - 1)) {
                comb.add(head);
                result.add(comb);
            }
        }
        return result;
    }
 
    public static void main(String[] args)
    {
        System.out.println(
            checkIfXExists(4, 2)); // Output: true
    }
}

Output

True

Time Complexity: The time complexity of this algorithm is O(n^2 log n) where n is the input number.

Auxiliary Space: The auxiliary space required by this algorithm is O(n) where n is the input number.

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 neveropen!

Check if a number exists having exactly N factors and K prime factors

C++

Java

Python3

C#

Javascript

Approach: “Factorization Approach”

C++

Python3

C#

Javascript

Java

Is MCP Already Outdated? The Real Reason Anthropic Shipped Skills—and How to Pair Them with Milvus

Unlocking 8× Milvus Performance with Cloudian HyperStore and NVIDIA RDMA for S3 Storage

Power high performance RAG for GenAI with HPE Alletra Storage MP + Milvus

LEAVE A REPLY Cancel reply

Most Popular

Google is working on vertical tabs for Chrome

Gemini can now tell you whether that image is real or AI-generated

Google Phone could soon let urgent calls cut through DND

Google AI Mode brings an unwelcome surprise as ads start populating searches

EDITOR PICKS

Google is working on vertical tabs for Chrome

Gemini can now tell you whether that image is real or AI-generated

Google Phone could soon let urgent calls cut through DND

POPULAR POSTS

Google is working on vertical tabs for Chrome

Gemini can now tell you whether that image is real or AI-generated

Google Phone could soon let urgent calls cut through DND

POPULAR CATEGORY

ABOUT US

FOLLOW US