Cerința

Definim un număr ca fiind fantastic dacă numărul de numere la care acesta se împarte exact este un număr prim.

Dându-se un șir cu n numere întregi strict pozitive, să se afișeze numărul de numere fantastice din șir.

Date de intrare

Fișierul de intrare fantastice.in conține pe prima linie numărul n de numere, iar pe cea de-a doua linie, separate prin câte un spaţiu, cele n numere.

Date de ieșire

Fișierul de ieșire fantastice.out va conține pe prima linie numărul de numere fantastice din șir.

Restricții și precizări

• 1 ≤ n ≤ 106
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici sau egale cu 106

Exemplu

fantastice.in

6
21 19 25 16 27 729

fantastice.out

4

Explicație

21 are divizorii 1, 3, 7, 21
19 are divizorii 1, 19
25 are divizorii 1, 5, 25
16 are divizorii 1, 2, 4, 8, 16
27 are divizorii 1, 3, 9, 27
729 are divizorii 1, 3, 9, 27, 81, 243, 729

Deci sunt 4 numere fantastice: 19 25 16 729

#include <bits/stdc++.h>
using namespace std;
ifstream fin("fantastice.in");
ofstream fout("fantastice.out");
int prim(int n)
{
    if(n==0 || n==1) return 0;
    if(n==2) return 1;
    if(n%2==0) return 0;
    else for(int d=3;d*d<=n;d+=2) if(n%d==0) return 0;
    return 1;
}
int nrdiv(int n)
{
    int cnt=0;
    for(int i=1;i*i<=n;i++)
    {
        if(n%i==0) cnt+=2;
        if(i*i==n) cnt--;
    }
    if(prim(cnt)) return 1;
    else return 0;
}
int main()
{
    int n,x,cnt=0,p=-10000;
    fin>>n;
    for(int i=0;i<n;i++)
    {
            fin>>x;
            if(nrdiv(x)) cnt++;
    }
    fout<<cnt;
    return 0;
}