Given an array arr[] consisting of N positive integers, the task is to find the number of array elements whose count of divisors is a prime number.
Examples:
Input: arr[] = {3, 6, 4}
Output: 2
Explanation:
The count of divisors for each element are:
- arr[0]( = 3): 3 has 2 divisors i.e., 1 and 3.
- arr[1]( = 6): 6 has 4 divisors i.e., 1, 2, 3, and 6.
- arr[2]( = 4): 4 has 3 divisors i.e., 1, 2, and 4.
Therefore, there are only 2 array elements, i.e. {3, 4}, whose count of divisors is a prime number.
Input: arr[] = {10, 13, 17, 25}
Output: 3
Naive Approach: The simplest approach to solve the given problem is to find the number of divisors for each array element and check if the count of divisors is a prime number or not. If found to be true, then increment the count. Otherwise, check for the next element. After checking for all array elements, print the count obtained.
Time Complexity: O(N(3/2))
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by precomputing the Prime Numbers using Sieve of Eratosthenes. Follow the steps below to solve the given problem:
- Initialize a variable, say count, to store the count of array elements whose count of divisors is a prime number.
- Store all prime numbers upto the maximum element of the array in a boolean array, say prime[], using Sieve of Eratosthenes.
- Now find the count of divisors of elements up to the maximum element of the array and store them in an array, say countDivisor[].
- Traverse the given array arr[] and for each element arr[i] and if the value of countDivisor[arr[i]] is prime, then increment the count by 1. Otherwise, check for the next element.
- After completing the above steps, print the value of count as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the array elements// whose count of divisors is primeint primeDivisors(int arr[], int N){ // Stores the maximum element int K = arr[0]; // Find the maximum element for (int i = 1; i < N; i++) { K = max(K, arr[i]); } // Store if i-th element is // prime(0) or non-prime(1) int prime[K + 1] = { 0 }; // Base Case prime[0] = 1; prime[1] = 1; for (int i = 2; i < K + 1; i++) { // If i is a prime number if (!prime[i]) { // Mark all multiples // of i as non-prime for (int j = 2 * i; j < K + 1; j += i) { prime[j] = 1; } } } // Stores the count of divisors int factor[K + 1] = { 0 }; // Base Case factor[0] = 0; factor[1] = 1; for (int i = 2; i < K + 1; i++) { factor[i] += 1; // Iterate to count factors for (int j = i; j < K + 1; j += i) { factor[j] += 1; } } // Stores the count of array // elements whose count of // divisors is a prime number int count = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // If count of divisors is prime if (prime[factor[arr[i]]] == 0) count++; } // Return the resultant count return count;}// Driver Codeint main(){ int arr[] = { 10, 13, 17, 25 }; int N = sizeof(arr) / sizeof(arr[0]); cout << primeDivisors(arr, N); return 0;} |
Java
// Java program for the above approachpublic class GFG{ // Function to count the array elements // whose count of divisors is prime public static int primeDivisors(int[] arr, int N) { // Stores the maximum element int K = arr[0]; // Find the maximum element for (int i = 1; i < N; i++) { K = Math.max(K, arr[i]); } // Store if i-th element is // prime(0) or non-prime(1) int[] prime = new int[K + 1]; // Base Case prime[0] = 1; prime[1] = 1; for (int i = 2; i < K + 1; i++) { // If i is a prime number if (prime[i] == 0) { // Mark all multiples // of i as non-prime for (int j = 2 * i; j < K + 1; j += i) { prime[j] = 1; } } } // Stores the count of divisors int[] factor = new int[K + 1]; // Base Case factor[0] = 0; factor[1] = 1; for (int i = 2; i < K + 1; i++) { factor[i] += 1; // Iterate to count factors for (int j = i; j < K + 1; j += i) { factor[j] += 1; } } // Stores the count of array // elements whose count of // divisors is a prime number int count = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // If count of divisors is prime if (prime[factor[arr[i]]] == 0) count++; } // Return the resultant count return count; } // Driver Code public static void main(String args[]) { int[] arr = { 10, 13, 17, 25 }; int N = arr.length; System.out.println(primeDivisors(arr, N)); }}// This code is contributed by SoumikMondal. |
Python3
# Python3 program for the above approach# Function to count the array elements# whose count of divisors is primedef primeDivisors(arr, N): # Stores the maximum element K = arr[0] # Find the maximum element for i in range(1, N): K = max(K, arr[i]) # Store if i-th element is # prime(0) or non-prime(1) prime = [0] * (K + 1) # Base Case prime[0] = 1 prime[1] = 1 for i in range(2, K + 1): # If i is a prime number if (not prime[i]): # Mark all multiples # of i as non-prime for j in range(2 * i, K + 1, i): prime[j] = 1 # Stores the count of divisors factor = [0] * (K + 1) # Base Case factor[0] = 0 factor[1] = 1 for i in range(2, K + 1): factor[i] += 1 # Iterate to count factors for j in range(i, K + 1, i): factor[j] += 1 # Stores the count of array # elements whose count of # divisors is a prime number count = 0 # Traverse the array arr[] for i in range(N): # If count of divisors is prime if (prime[factor[arr[i]]] == 0): count += 1 # Return the resultant count return count# Driver Codeif __name__ == '__main__': arr = [ 10, 13, 17, 25 ] N = len(arr) print (primeDivisors(arr, N))# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{ // Function to count the array elements // whose count of divisors is prime static int primeDivisors(int[] arr, int N) { // Stores the maximum element int K = arr[0]; // Find the maximum element for (int i = 1; i < N; i++) { K = Math.Max(K, arr[i]); } // Store if i-th element is // prime(0) or non-prime(1) int[] prime = new int[K + 1]; // Base Case prime[0] = 1; prime[1] = 1; for (int i = 2; i < K + 1; i++) { // If i is a prime number if (prime[i] == 0) { // Mark all multiples // of i as non-prime for (int j = 2 * i; j < K + 1; j += i) { prime[j] = 1; } } } // Stores the count of divisors int[] factor = new int[K + 1]; // Base Case factor[0] = 0; factor[1] = 1; for (int i = 2; i < K + 1; i++) { factor[i] += 1; // Iterate to count factors for (int j = i; j < K + 1; j += i) { factor[j] += 1; } } // Stores the count of array // elements whose count of // divisors is a prime number int count = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // If count of divisors is prime if (prime[factor[arr[i]]] == 0) count++; } // Return the resultant count return count; } // Driver Code public static void Main() { int[] arr = { 10, 13, 17, 25 }; int N = arr.Length; Console.WriteLine(primeDivisors(arr, N)); }}// This code is contributed by ukasp. |
Javascript
<script>// JavaScript program for the above approach// Function to count the array elements// whose count of divisors is primefunction primeDivisors(arr, N){ // Stores the maximum element var K = arr[0]; var i,j; // Find the maximum element for (i = 1; i < N; i++) { K = Math.max(K, arr[i]); } // Store if i-th element is // prime(0) or non-prime(1) var prime = Array(K + 1).fill(0); // Base Case prime[0] = 1; prime[1] = 1; for (i = 2; i < K + 1; i++) { // If i is a prime number if (prime[i]==0) { // Mark all multiples // of i as non-prime for (j = 2 * i; j < K + 1; j += i) { prime[j] = 1; } } } // Stores the count of divisors var factor = Array(K + 1).fill(0); // Base Case factor[0] = 0; factor[1] = 1; for (i = 2; i < K + 1; i++) { factor[i] += 1; // Iterate to count factors for (j = i; j < K + 1; j += i) { factor[j] += 1; } } // Stores the count of array // elements whose count of // divisors is a prime number var count = 0; // Traverse the array arr[] for (i = 0; i < N; i++) { // If count of divisors is prime if (prime[factor[arr[i]]] == 0) count++; } // Return the resultant count return count;}// Driver Code var arr = [10, 13, 17, 25]; var N = arr.length; document.write(primeDivisors(arr, N));</script> |
Output:
3
Time Complexity: O(M*log M), where M is the maximum element of the given array.
Auxiliary Space: O(M)
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!
