## Introduction

In this blog, we will discuss a number theory problem asked frequently in Interviews.

The problem is to c**ount array elements whose count of divisors is a prime number.**

### Problem Statement

Say we are given an array of n elements. We need to find number of elements whose all divisors are the prime number.

### Sample Example

**Example:**

```
Sample Input
3 6 4
Sample Output
2
```

**Explanation:**

```
Our array has 3 elements.
{3, 6, 4}
Divisor of 3 = 1,3.
count = 2 (prime number)
Divisor of 6 = 1,2,3,6.
count = 4 (not a prime number)
Divisor of 4 = 1,2,4
count = 3 (prime number)
So, our answer would be 2. We found 2 prime numbers in the count.
```

Also see, __Euclid GCD Algorithm__

## Approach

The** approach** to count array elements whose count of divisors is a prime number is given below. We have used the concept of the sieve of Eratosthenes to find the prime divisors of a number. After finding the prime divisors of a number, in an array, we will store the count of prime divisors found for each number. Then, we check if the number of counts obtained is a prime number or not and store the prime counts in a separate array and return the length of this array.

Declare a variable to store the maximum element

⬇

Find the maximum element.

⬇

Declare an array to store if i-th element is prime or non-prime. Also, define the base cases.

⬇

For all elements, if i is a prime number, Mark all multiples of i as non-prime.

⬇

Declare another array to store count of divisors. Also, define the base cases.

⬇

Iterate to count factors.

⬇

Declare a variable to store the count of array elements whose count of divisors is a prime number.

⬇

Traverse the array, if the count of divisors is prime, increment count.

⬇

Return count.

Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try.

Please have a look at the algorithm to count array elements whose count of divisors is a prime number, and then again, you must give it a try.

### PseudoCode

**Algorithm **

```
___________________________________________________________________
procedure primeDivisors(int arr[], int N):
___________________________________________________________________
1. K = arr[0]
2. For all elements in the given array, K = max(K, arr[i])
3. prime[K + 1] = { 0 }
4. prime[0] = 1, prime[1] = 1
5. Run loop from 2 till n:
if (!prime[i]): for ( j = 2 * i; j < K + 1; j += i) prime[j] = 1
6. factor[K + 1] = { 0 }
7. factor[0] = 0, factor[1] = 1
8. Run loop from 2 till n:
factor[i] += 1
for (j = i; j < K + 1; j = j+i):
factor[j] += 1
9. count = 0
10. Run loop from 0 till n:
if (prime[factor[arr[i]]] == 0):
Count++
11. Return count.
end procedure
```