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 = k1a + k2b + k3c + ... + knn
- 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 numberbool 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 factorsvoid 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 Codeint 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 factorsimport java.io.*; import java.util.*;class GFG{ // Function to compute the// number of factors of// the given numberstatic 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 factorsstatic 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 numberfunction 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 factorsfunction 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 Codelet n = 4;let k = 2;operation(n, k);</script> |
Output
Yes
Time Complexity: O(n1/2)
Auxiliary Space: O(n1/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 nvector<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 limitvector<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 nset<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 Codeint main(){ cout << check_if_x_exists(4, 2); return 0;} |
Python3
import itertoolsdef 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 factorsdef 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 primesdef 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 Falseprint(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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
