Count array elements having exactly K divisors
Given an array arr[] consisting of N integers and an integer K, the task is to count the number of array elements having exactly K divisors.
Examples:
Input: N = 5, arr[] = { 3, 6, 2, 9, 4 }, K = 2
Output: 2
Explanation: arr[0] (= 3) and arr[2] (= 2) have exactly 2 divisors.Input: N = 5, arr[] = { 3, 6, 2, 9, 4 }, K = 3
Output: 2
Explanation: arr[3] (= 9) and arr[4] (= 4) have exactly 3 divisors
Approach: The idea to solve this problem is to compute the total number of divisors of each array element and store them in a Map. Then, traverse the array and for every array element, check if has exactly K divisors. Print the count of such numbers. Follow the steps below to solve the problem:
- Find the maximum element present in the array.
- Initialize an array prime[].
- Store all primes present in the range [2, maximum element in the array] in the array prime[] using Sieve of Eratosthenes.
- Traverse the array and prime factorize each array element using the given formula:
where ai are prime factors and pi are integral powers to which they are raised.
- Count the total number of the divisors of each array element using the following formula:
- Initialize a Map to store the total number of divisors of each array element.
- Traverse the array and initialize a variable, say, count, to count the number of elements having exactly K total number of divisors.
- Print the number of elements having exactly K divisors.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Stores prime numbers // using Sieve of Eratosthenes bool prime[100000]; // Function to find the maximum element int maximumElement( int arr[], int N) { // Stores the maximum element // of the array int max = arr[0]; // Traverse the array for ( int i = 0; i < N; i++) { // If current element // is maximum so far if (max < arr[i]) { // Update maximum max = arr[i]; } } // Return maximum element return max; } // Function to find the prime numbers // using sieve of eratosthenes algorithm void sieveOfEratosthenes( int max) { // Calculate primes using Sieve memset (prime, true , max+1); for ( int p = 2; p * p < max; p++) // If current element is prime if (prime[p] == true ) // Make all multiples non-prime for ( int i = p * 2; i < max; i += p) prime[i] = false ; } // Function to count divisors of n int divCount( int n) { // Traversing through // all prime numbers int total = 1; for ( int p = 2; p <= n; p++) { // If it is a prime number if (prime[p]) { // Calculate number of divisors // with the formula // number of divisors = (p1 + 1) * (p2 + 1) // *.....* (pn + 1) // n = (a1 ^ p1) * (a2 ^ p2) .... *(an ^ pn) // ai: prime divisor of n // pi: power in factorization int count = 0; if (n % p == 0) { while (n % p == 0) { n = n / p; count++; } total = total * (count + 1); } } } // Return the total number of divisors return total; } // Function to count array elements // having exactly K divisors int countElements( int arr[], int N, int K) { // Initialize a map to store // count of divisors of array elements map< int , int > map; // Traverse the array for ( int i = 0; i < N; i++) { // If element is not already present in // the Map, then insert it into the Map if (map.find(arr[i]) == map.end()) { // Function call to count the total // number of divisors map.insert({arr[i], divCount(arr[i])}); } } // Stores the number of // elements with divisor K int count = 0; // Traverse the array for ( int i = 0; i < N; i++) { // If current element // has exactly K divisors if (map.at(arr[i]) == K) { count++; } } // Return the number of // elements having K divisors return count; } // Driver Code int main() { int arr[] = { 3, 6, 2, 9, 4 }; int N = sizeof (arr) / sizeof (arr[0]); int K = 2; // Find the maximum element int max = maximumElement(arr, N); // Generate all prime numbers sieveOfEratosthenes(max); cout << countElements(arr, N, K); return 0; } // This code is contributed by Dharanendra L V |
Java
// Java program for the above approach import java.util.*; class GFG { // Stores prime numbers // using Sieve of Eratosthenes public static boolean prime[]; // Function to find the maximum element public static int maximumElement( int arr[], int N) { // Stores the maximum element // of the array int max = arr[ 0 ]; // Traverse the array for ( int i = 0 ; i < N; i++) { // If current element // is maximum so far if (max < arr[i]) { // Update maximum max = arr[i]; } } // Return maximum element return max; } // Function to find the prime numbers // using sieve of eratosthenes algorithm public static void sieveOfEratosthenes( int max) { // Initialize primes having // size of maximum element + 1 prime = new boolean [max + 1 ]; // Calculate primes using Sieve Arrays.fill(prime, true ); for ( int p = 2 ; p * p < max; p++) // If current element is prime if (prime[p] == true ) // Make all multiples non-prime for ( int i = p * 2 ; i < max; i += p) prime[i] = false ; } // Function to count divisors of n public static int divCount( int n) { // Traversing through // all prime numbers int total = 1 ; for ( int p = 2 ; p <= n; p++) { // If it is a prime number if (prime[p]) { // Calculate number of divisors // with the formula // number of divisors = (p1 + 1) * (p2 + 1) // *.....* (pn + 1) // n = (a1 ^ p1) * (a2 ^ p2) .... *(an ^ pn) // ai: prime divisor of n // pi: power in factorization int count = 0 ; if (n % p == 0 ) { while (n % p == 0 ) { n = n / p; count++; } total = total * (count + 1 ); } } } // Return the total number of divisors return total; } // Function to count array elements // having exactly K divisors public static int countElements( int arr[], int N, int K) { // Initialize a map to store // count of divisors of array elements Map<Integer, Integer> map = new HashMap<Integer, Integer>(); // Traverse the array for ( int i = 0 ; i < N; i++) { // If element is not already present in // the Map, then insert it into the Map if (!map.containsKey(arr[i])) { // Function call to count the total // number of divisors map.put(arr[i], divCount(arr[i])); } } // Stores the number of // elements with divisor K int count = 0 ; // Traverse the array for ( int i = 0 ; i < N; i++) { // If current element // has exactly K divisors if (map.get(arr[i]) == K) { count++; } } // Return the number of // elements having K divisors return count; } // Driver Code public static void main( String[] args) { int arr[] = { 3 , 6 , 2 , 9 , 4 }; int N = arr.length; int K= 2 ; // Find the maximum element int max = maximumElement(arr, N); // Generate all prime numbers sieveOfEratosthenes(max); System.out.println(countElements(arr, N, K)); } } |
Python3
# Python3 program for the above approach # Stores prime numbers # using Sieve of Eratosthenes # Function to find the maximum element def maximumElement(arr, N): # Stores the maximum element # of the array max = arr[ 0 ] # Traverse the array for i in range (N): # If current element # is maximum so far if ( max < arr[i]): # Update maximum max = arr[i] # Return maximum element return max # Function to find the prime numbers # using sieve of eratosthenes algorithm def sieveOfEratosthenes( max ): global prime for p in range ( 2 , max + 1 ): if p * p > max : break # If current element is prime if (prime[p] = = True ): # Make all multiples non-prime for i in range ( 2 * p, max , p): prime[i] = False return prime # Function to count divisors of n def divCount(n): # Traversing through # all prime numbers total = 1 for p in range ( 2 , n + 1 ): # If it is a prime number if (prime[p]): # Calculate number of divisors # with the formula # number of divisors = (p1 + 1) * (p2 + 1) # *.....* (pn + 1) # n = (a1 ^ p1) * (a2 ^ p2) .... *(an ^ pn) # ai: prime divisor of n # pi: power in factorization count = 0 if (n % p = = 0 ): while (n % p = = 0 ): n = n / / p count + = 1 total = total * (count + 1 ) # Return the total number of divisors return total # Function to count array elements # having exactly K divisors def countElements(arr, N, K): # Initialize a map to store # count of divisors of array elements mp = {} # Traverse the array for i in range (N): # If element is not already present in # the Map, then insert it into the Map if (arr[i] not in mp): # Function call to count the total # number of divisors mp[arr[i]] = divCount(arr[i]) # Stores the number of # elements with divisor K count = 0 # Traverse the array for i in range (N): # If current element # has exactly K divisors if (mp[arr[i]] = = K): count + = 1 # Return the number of # elements having K divisors return count # Driver Code if __name__ = = '__main__' : prime = [ True for i in range ( 10 * * 6 )] arr = [ 3 , 6 , 2 , 9 , 4 ] N = len (arr) K = 2 # Find the maximum element max = maximumElement(arr, N) # Generate all prime numbers prime = sieveOfEratosthenes( max ) print (countElements(arr, N, K)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Stores prime numbers // using Sieve of Eratosthenes public static bool []prime; // Function to find the maximum element public static int maximumElement( int []arr, int N) { // Stores the maximum element // of the array int max = arr[0]; // Traverse the array for ( int i = 0; i < N; i++) { // If current element // is maximum so far if (max < arr[i]) { // Update maximum max = arr[i]; } } // Return maximum element return max; } // Function to find the prime numbers // using sieve of eratosthenes algorithm public static void sieveOfEratosthenes( int max) { // Initialize primes having // size of maximum element + 1 prime = new bool [max + 1]; // Calculate primes using Sieve for ( int i = 0; i < prime.Length; i++) prime[i] = true ; for ( int p = 2; p * p < max; p++) // If current element is prime if (prime[p] == true ) // Make all multiples non-prime for ( int i = p * 2; i < max; i += p) prime[i] = false ; } // Function to count divisors of n public static int divCount( int n) { // Traversing through // all prime numbers int total = 1; for ( int p = 2; p <= n; p++) { // If it is a prime number if (prime[p]) { // Calculate number of divisors // with the formula // number of divisors = (p1 + 1) * (p2 + 1) // *.....* (pn + 1) // n = (a1 ^ p1) * (a2 ^ p2) .... *(an ^ pn) // ai: prime divisor of n // pi: power in factorization int count = 0; if (n % p == 0) { while (n % p == 0) { n = n / p; count++; } total = total * (count + 1); } } } // Return the total number of divisors return total; } // Function to count array elements // having exactly K divisors public static int countElements( int []arr, int N, int K) { // Initialize a map to store // count of divisors of array elements Dictionary< int , int > map = new Dictionary< int , int >(); // Traverse the array for ( int i = 0; i < N; i++) { // If element is not already present in // the Map, then insert it into the Map if (!map.ContainsKey(arr[i])) { // Function call to count the total // number of divisors map.Add(arr[i], divCount(arr[i])); } } // Stores the number of // elements with divisor K int count = 0; // Traverse the array for ( int i = 0; i < N; i++) { // If current element // has exactly K divisors if (map[arr[i]] == K) { count++; } } // Return the number of // elements having K divisors return count; } // Driver Code public static void Main(String[] args) { int []arr = {3, 6, 2, 9, 4}; int N = arr.Length; int K= 2; // Find the maximum element int max = maximumElement(arr, N); // Generate all prime numbers sieveOfEratosthenes(max); Console.WriteLine(countElements(arr, N, K)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for the above approach // Stores prime numbers // using Sieve of Eratosthenes let prime = new Array(100000); // Function to find the maximum element function maximumElement(arr, N) { // Stores the maximum element // of the array let max = arr[0]; // Traverse the array for (let i = 0; i < N; i++) { // If current element // is maximum so far if (max < arr[i]) { // Update maximum max = arr[i]; } } // Return maximum element return max; } // Function to find the prime numbers // using sieve of eratosthenes algorithm function sieveOfEratosthenes(max) { // Calculate primes using Sieve prime.fill( true , 0, max + 1) for (let p = 2; p * p < max; p++) // If current element is prime if (prime[p] == true ) // Make all multiples non-prime for (let i = p * 2; i < max; i += p) prime[i] = false ; } // Function to count divisors of n function divCount(n) { // Traversing through // all prime numbers let total = 1; for (let p = 2; p <= n; p++) { // If it is a prime number if (prime[p]) { // Calculate number of divisors // with the formula // number of divisors = (p1 + 1) * (p2 + 1) // *.....* (pn + 1) // n = (a1 ^ p1) * (a2 ^ p2) .... *(an ^ pn) // ai: prime divisor of n // pi: power in factorization let count = 0; if (n % p == 0) { while (n % p == 0) { n = n / p; count++; } total = total * (count + 1); } } } // Return the total number of divisors return total; } // Function to count array elements // having exactly K divisors function countElements(arr, N, K) { // Initialize a map to store // count of divisors of array elements let map = new Map(); // Traverse the array for (let i = 0; i < N; i++) { // If element is not already present in // the Map, then insert it into the Map if (!map.has(arr[i])) { // Function call to count the total // number of divisors map.set(arr[i], divCount(arr[i])); } } // Stores the number of // elements with divisor K let count = 0; // Traverse the array for (let i = 0; i < N; i++) { // If current element // has exactly K divisors if (map.get(arr[i]) == K) { count++; } } // Return the number of // elements having K divisors return count; } // Driver Code let arr = [ 3, 6, 2, 9, 4 ]; let N = arr.length; let K = 2; // Find the maximum element let max = maximumElement(arr, N); // Generate all prime numbers sieveOfEratosthenes(max); document.write(countElements(arr, N, K)); // This code is contributed by _saurabh_jaiswal </script> |
2
Time Complexity: O(N + maxlog(log(max) + log(max)), where max is the maximum array element.
Auxiliary Space: O(max), where max is the maximum array element.
Contact Us