Count array elements whose count of divisors is a prime number

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.