Un număr natural se numește aproape prim dacă poate fi scris ca produs de două numere naturale prime distincte.

Cerinţa

Se citește un număr natural și apoi n numere naturale. Să se determine câte dintre ele sunt aproape prime.

Date de intrare

Programul citește de la tastatură numărul n, și apoi n numere naturale.

Date de ieşire

Programul afișează pe ecran numărul C, reprezentând câte dintre numerele citite sunt aproape prime.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• cele n numere citite sunt cuprinse între 1 și 1.000.000.000

Exemplu

Intrare

6
35 55 12 6 25 50

Ieșire

3

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

int main()
{
    int n;
    cin >> n;
    int cnt = 0;
    for(int i = 1; i <= n; ++i){
        int x;
        cin >> x;
        int d = 2;
        int cn = 1;
        while(x > 1){
            int p = 0;
            while(x % d == 0)
                p++, x/=d;
            d++;
            cn = cn * (p + 1);
            if(d * d > x)
                d = x;
        }
        if(cn == 4)
            cnt ++;
    }
    cout << cnt;
    return 0;
}