1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Approach
2.1.
PseudoCode
3.
Implementation in C++
3.1.
Complexity Analysis
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

# Count array elements whose count of divisors is a prime number

Urwashi Priya
0 upvote

## Introduction

In this blog, we will discuss a number theory problem asked frequently in Interviews.
The problem is to count 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.

try here

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``````

## Implementation in C++

``````// C++ program to count array elements whose count of divisors is a prime number

#include <bits/stdc++.h>
using namespace std;

int primeDivisors(int arr[], int N)
{
// a variable to store the maximum element
int K = arr[0];

// Finding the maximum or the largest element
for (int i = 1; i < N; i++) {
K = max(K, arr[i]);
}

// Store if i-th element is prime or non-prime
int prime[K + 1] = { 0 };

//0th index
prime[0] = 1;

//first index
prime[1] = 1;

//iterating the loop
for (int i = 2; i < K + 1; i++) {

//i being a prime number then
if (!prime[i]) {

// Marking all multiples of i(in succession) as non-prime numbers
for (int j = 2 * i; j < K + 1; j += i) {
prime[j] = 1;
}
}
}

// array to store the count of divisors obtained
int factor[K + 1] = { 0 };

factor[0] = 0;
factor[1] = 1;
//iterating from 0 till k+1.
for (int i = 2; i < K + 1; i++) {
//incrementing factor[j]
factor[i] += 1;

// Iterating to count number of factors of each number
for (int j = i; j < K + 1; j += i) {
//incrementing factor[j]
factor[j] += 1;
}
}

// Storing 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 count;
}

int main()
{
int N;
cin>>N;
int arr[N];
for(int i=0; i<N; i++){
cin>>arr[i];
}
cout << primeDivisors(arr, N);

return 0;
}
``````

Output:

``````Sample Input:
4
10 13 17 25

Sample Output:
3``````

### Complexity Analysis

Time Complexity: O(N*log N).

Analysing Time Complexity:

All n elements are traversed once and then log N times. N is the largest element of the array.

Space complexity: O(N). N size array is used to store the count of prime divisors.

## FAQs

1. What is the sieve of Eratosthenes?
A method for extracting prime numbers that involve listing down the odd numbers from 2 up in succession and passing out every 3rd number after 3, every 5th number after 5 including those already passed out, every 7th after 7, and so on with the numbers that are never passed out being prime.

2. What is the purpose of number theory?
It is used to study and figure out the various relations between different numbers and prove those relationships.

3.  Is the sieve of Eratosthenes an example of dynamic programming?
Yes.

## Key Takeaways

This article taught us how to count array elements whose count of divisors is a prime number by approaching the problem using the modular exponentiation concept. We discussed our problem's implementation using illustrations, pseudocode, and proper code.

We hope you could easily take away all critical and conceptual techniques like analysing problems by walking over the execution of the given examples and finding out the pattern followed.

Now, we strongly recommend you practice problem sets based on number theory to master your fundamentals and enhance your learning. You can get a wide range and variety of questions similar to this on Coding Ninjas Studio

It's not the end. Must solve the problem of similar types.

Happy Coding.

Live masterclass