Các phần tử của mảng có tần số nguyên tố?

Giả sử chúng ta có một mảng. chúng ta phải đếm xem có bao nhiêu phần tử hiện diện trong mảng với số lần nguyên tố. Vì vậy, nếu mảng là {1, 2, 2, 0, 1, 5, 2, 5, 0, 0, 1, 1}, thì 1 có mặt 4 lần, 2 có mặt 3 lần, 0 có mặt 3 lần, và 5 có mặt 2 lần. Vậy có ba phần tử {2, 0, 5} đồng thời là số nguyên tố. Vì vậy, số lượng sẽ là 3.

Thuật toán

countPrimeOcchood (arr, n)

Begin
   count := 0
   define map with int type key and int type value
   for each element e in arr, do
      increase map.key(arr).value
   done
   for each key check whether the value corresponding the value is prime or not, if prime, then increase count.
   return count
End

Ví dụ

#include <iostream>
#include <map>
using namespace std;
bool isPrime(int n){
   for(int i = 2; i<=n/2; i++){
      if(n % i == 0){
         return false;
      }
   }
   return true;
}
int countPrimeOcurrence(int arr[], int n){
   int count = 0;
   map<int, int> freq_map;
   for(int i = 0; i<n; i++){
      freq_map[arr[i]]++; //increase the frequency
   }
   for (auto it = freq_map.begin(); it != freq_map.end(); it++) {
      if (isPrime(it->second))
         count++;
   }
   return count;
}
int main() {
   int arr[] = {1, 2, 2, 0, 1, 5, 2, 5, 0, 0, 1, 1};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Prime frequency count: " << countPrimeOcurrence(arr, n);
}

Đầu ra

Prime frequency count: 3