Cerința

Se dau n numere naturale. Determinați câte dintre ele sunt prime.

Date de intrare

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

Date de ieșire

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

Restricții și precizări

• 1 ≤ n ≤ 1000
• cele n numere citite vor fi mai mici decât 1.000.000.000

Exemplu

Intrare

5
11 25 3 4 1

Ieșire

2

Explicație

Dintre cele 5 numere citite sunt prime numerele 11 și 3.

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

bool prim(int x){
    int d = 2, cnt = 1;
    while(x > 1){
        int p = 0;
        while(x % d == 0)
            p++, x/=d;
        cnt *= (p + 1);
        d++;
        if(d * d > x)
            d = x;
    }
    return cnt == 2;
}

int main(){
    int n, x, cnt = 0;
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> x;
        if(prim(x))
            cnt++;
    }
    cout << cnt;
    return 0;
}