Check if a number exists with X divisors out of which Y are composite

0 0 5 minutes read

Given two integers X and Y representing the total number of divisors and the number of composite divisors respectively, the task is to check if there exists an integer N which has exactly X divisors and Y are composite numbers.

Examples:

Input: X = 6, Y = 3
Output: YES
Explanation:
N = 18 is such a number.
The divisors of 18 are 1, 2, 3, 6, 9 and 18.
The composite divisors of 18 are 6, 9 and 18.
Input: X = 7, Y = 3
Output: NO
Explanation:
We see that no such number exists that has 7 positive divisors out of which 3 are composite divisors.

Approach:

Firstly calculate the number of prime divisors of a number, which is equal to:

Number of prime divisors = Total number of divisors – Number of composite divisors – 1

So, the number of prime divisors, C = X – Y – 1
Since every number has 1 as a factor and 1 is neither a prime number nor a composite number, we have to exclude it from being counted in the number of prime divisors.
If the number of composite divisors is less than the number of prime divisors, then it is not possible to find such a number at all.
So if the prime factorization of X contains at least C distinct integers, then a solution is possible. Otherwise, we cannot find a number N that will satisfy the given conditions.
Find the maximum number of values X can be decomposed into such that each value is greater than 1. In other words, we can find out the prime factorization of X.
If that prime factorization has a number of terms greater than or equal to C, then such a number is possible.

Below is the implementation of the above approach:

C++

// C++ program to check if a number
// exists having exactly X positive
// divisors out of which Y are
// composite divisors
#include <bits/stdc++.h>
using namespace std;
 
int factorize(int N)
{
    int count = 0;
    int cnt = 0;
 
    // Count the number of
    // times 2 divides N
    while ((N % 2) == 0) {
        N = N / 2;
        count++;
    }
 
    cnt = cnt + count;
 
    // check for all possible
    // numbers that can divide it
    for (int i = 3; i <= sqrt(N); i += 2) {
        count = 0;
        while (N % i == 0) {
            count++;
            N = N / i;
        }
        cnt = cnt + count;
    }
 
    // if N at the end
    // is a prime number.
    if (N > 2)
        cnt = cnt + 1;
    return cnt;
}
 
// Function to check if any
// such number exists
void ifNumberExists(int X, int Y)
{
    int C, dsum;
 
    C = X - Y - 1;
    dsum = factorize(X);
    if (dsum >= C)
        cout << "YES \n";
    else
        cout << "NO \n";
}
 
// Driver Code
int main()
{
 
    int X, Y;
    X = 6;
    Y = 4;
 
    ifNumberExists(X, Y);
    return 0;
}

Java

// Java program to check if a number 
// exists having exactly X positive 
// divisors out of which Y are 
// composite divisors 
import java.lang.Math;
class GFG{
     
public static int factorize(int N) 
{ 
    int count = 0; 
    int cnt = 0; 
     
    // Count the number of 
    // times 2 divides N 
    while ((N % 2) == 0)
    { 
        N = N / 2; 
        count++; 
    } 
     
    cnt = cnt + count; 
     
    // Check for all possible 
    // numbers that can divide it 
    for(int i = 3; i <= Math.sqrt(N); i += 2)
    { 
       count = 0; 
       while (N % i == 0)
       { 
           count++; 
           N = N / i; 
       } 
       cnt = cnt + count; 
    } 
     
    // If N at the end 
    // is a prime number. 
    if (N > 2) 
        cnt = cnt + 1; 
    return cnt; 
} 
     
// Function to check if any 
// such number exists 
public static void ifNumberExists(int X, int Y) 
{ 
    int C, dsum; 
    C = X - Y - 1; 
    dsum = factorize(X); 
         
    if (dsum >= C) 
        System.out.println("YES");
    else
        System.out.println("NO");
} 
 
// Driver code    
public static void main(String[] args)
{
    int X, Y; 
    X = 6; 
    Y = 4; 
     
    ifNumberExists(X, Y); 
}
}
 
// This code is contributed by divyeshrabadiya07

Python3

# Python3 program to check if a number exists 
# having exactly X positive divisors out of
#  which Y are composite divisors
import math 
 
def factorize(N):
 
    count = 0
    cnt = 0
 
    # Count the number of
    # times 2 divides N
    while ((N % 2) == 0):
        N = N // 2
        count+=1
 
    cnt = cnt + count
 
    # Check for all possible
    # numbers that can divide it
    sq = int(math.sqrt(N))
    for i in range(3, sq, 2):
        count = 0
         
        while (N % i == 0):
            count += 1
            N = N // i
         
        cnt = cnt + count
 
    # If N at the end
    # is a prime number.
    if (N > 2):
        cnt = cnt + 1
    return cnt
 
# Function to check if any
# such number exists
def ifNumberExists(X, Y):
 
    C = X - Y - 1
    dsum = factorize(X)
     
    if (dsum >= C):
        print ("YES")
    else:
        print("NO")
 
# Driver Code
if __name__ == "__main__":
     
    X = 6
    Y = 4
 
    ifNumberExists(X, Y)
 
# This code is contributed by chitranayal

C#

// C# program to check if a number 
// exists having exactly X positive 
// divisors out of which Y are 
// composite divisors 
using System;
class GFG{ 
 
public static int factorize(int N) 
{ 
    int count = 0; 
    int cnt = 0; 
     
    // Count the number of 
    // times 2 divides N 
    while ((N % 2) == 0) 
    { 
        N = N / 2; 
        count++; 
    } 
     
    cnt = cnt + count; 
     
    // Check for all possible 
    // numbers that can divide it 
    for(int i = 3; i <= Math.Sqrt(N); i += 2) 
    { 
        count = 0; 
        while (N % i == 0) 
        { 
            count++; 
            N = N / i; 
        } 
        cnt = cnt + count; 
    } 
     
    // If N at the end 
    // is a prime number. 
    if (N > 2) 
        cnt = cnt + 1; 
    return cnt; 
} 
     
// Function to check if any 
// such number exists 
public static void ifNumberExists(int X, int Y) 
{ 
    int C, dsum; 
    C = X - Y - 1; 
    dsum = factorize(X); 
         
    if (dsum >= C) 
        Console.WriteLine("YES"); 
    else
        Console.WriteLine("NO"); 
} 
 
// Driver code 
public static void Main(string[] args) 
{ 
    int X, Y; 
    X = 6; 
    Y = 4; 
     
    ifNumberExists(X, Y); 
} 
} 
 
// This code is contributed by AnkitRai01

Javascript

<script>
// javascript program to check if a number 
// exists having exactly X positive 
// divisors out of which Y are 
// composite divisors 
 
    function factorize(N) {
        var count = 0;
        var cnt = 0;
 
        // Count the number of
        // times 2 divides N
        while ((N % 2) == 0) {
            N = N / 2;
            count++;
        }
 
        cnt = cnt + count;
 
        // Check for all possible
        // numbers that can divide it
        for (i = 3; i <= Math.sqrt(N); i += 2) {
            count = 0;
            while (N % i == 0) {
                count++;
                N = N / i;
            }
            cnt = cnt + count;
        }
 
        // If N at the end
        // is a prime number.
        if (N > 2)
            cnt = cnt + 1;
        return cnt;
    }
 
    // Function to check if any
    // such number exists
    function ifNumberExists(X , Y) {
        var C, dsum;
        C = X - Y - 1;
        dsum = factorize(X);
 
        if (dsum >= C)
            document.write("YES");
        else
            document.write("NO");
    }
 
    // Driver code
     
        var X, Y;
        X = 6;
        Y = 4;
 
        ifNumberExists(X, Y);
 
// This code is contributed by todaysgaurav
</script>

Output:

YES

Time Complexity: O (N^1/2)
Auxiliary Space: O (1)

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!