Check if a number exists with X divisors out of which Y are composite
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> |
YES
Time Complexity: O (N 1/2)
Auxiliary Space: O (1)