jocprim_Of2

#include <bits/stdc++.h>

using namespace std;

#define NN 10000000

ifstream f("jocprim.in");
ofstream g("jocprim.out");

int v[NN + 1];

int maxPrimeFactors(int  n)
{
    int maxPrime = -1;
    while (n % 2 == 0) {
        maxPrime = 2;
        n >>= 1;
    }
    for (int i = 3; i <= sqrt(n); i += 2) {
        while (n % i == 0)
        {
            maxPrime = i;
            n = n / i;
        }
    }

    if (n > 2)
        maxPrime = n;

    return maxPrime;
}

int main() {

  int n, x, i, cnt = 0;
  f >> n;
  while (n--)
  {
    f >> x;
    if(v[maxPrimeFactors(x)]==0)
        cnt++;
    v[maxPrimeFactors(x)]++;
  }
  g << cnt << '\n'; //afisam numarul de perechi
  for (i = 2; i <= NN; i++) //afisam perechile
    if (v[i]) //daca i este cel mai mare divizor prim pentru cel putin unul din termenii sirului
      g << i << " " << v[i] << '\n'; // afisam i si frecventa acestuia

  f.close();
  g.close();

  return 0;
}