Count array elements whose count of divisors is a prime number | C ++ program for the above approach ; Function to count the array elements whose count of divisors is prime ; Stores the maximum element ; Find the maximum element ; Store if i - th element is prime ( 0 ) or non - prime ( 1 ) ; Base Case ; If i is a prime number ; Mark all multiples of i as non - prime ; Stores the count of divisors ; Base Case ; Iterate to count factors ; Stores the count of array elements whose count of divisors is a prime number ; Traverse the array arr [ ] ; If count of divisors is prime ; Return the resultant count ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int primeDivisors ( int arr [ ] , int N ) { int K = arr [ 0 ] ; for ( int i = 1 ; i < N ; i ++ ) { K = max ( K , arr [ i ] ) ; } int prime [ K + 1 ] = { 0 } ; prime [ 0 ] = 1 ; prime [ 1 ] = 1 ; for ( int i = 2 ; i < K + 1 ; i ++ ) { if ( ! prime [ i ] ) { for ( int j = 2 * i ; j < K + 1 ; j += i ) { prime [ j ] = 1 ; } } } int factor [ K + 1 ] = { 0 } ; factor [ 0 ] = 0 ; factor [ 1 ] = 1 ; for ( int i = 2 ; i < K + 1 ; i ++ ) { factor [ i ] += 1 ; for ( int j = i ; j < K + 1 ; j += i ) { factor [ j ] += 1 ; } } int count = 0 ; for ( int i = 0 ; i < N ; i ++ ) { if ( prime [ factor [ arr [ i ] ] ] == 0 ) count ++ ; } return count ; } int main ( ) { int arr [ ] = { 10 , 13 , 17 , 25 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << primeDivisors ( arr , N ) ; return 0 ; }