Cerința

Se dau n numere naturale. Aflaţi câte dintre aceste numere sunt prime.

Date de intrare

Fișierul de intrare eratostene1.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire eratostene1.out va conține pe prima linie numărul numerelor prime aflate în fişierul de intrare.

Restricții și precizări

• 1 ≤ n ≤ 500.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemplu

eratostene1.in

7
12 29 33 47 51 7 19

eratostene1.out

4

Explicație

În fișierul de intrare sunt 4 numere prime: 29, 47, 7, 19.

#include <bits/stdc++.h>

using namespace std;

ifstream cin("eratostene1.in");
ofstream cout("eratostene1.out");

bitset<500001> p;

int main(){
    p[0]=1;
    for(int i = 3; i <= 999999; i+=2)
        if(p[i/2]==0)
            for(int j = 3 * i; j <= 999999; j += 2 * i)
                p[j/2] = 1;
    int n, k = 0;
    cin >> n;
    for(int i = 1; i <= n; ++i){
        int x;
        cin >> x;
        if(x % 2 == 0 && x == 2)
            k++;
        else if(x % 2 == 1 && p[x/2] == 0)
            k++;
    }
    cout << k;
    return 0;
}