Cerinţa

Se dau n numere naturale mai mici decât 1.000.000. Determinaţi câte dintre ele sunt prime.

Date de intrare

Fişierul de intrare eratostene.in conţine pe prima linie numărul n; urmează cele n numere, dispuse pe mai multe linii şi separate prin spaţii.

Date de ieşire

Fişierul de ieşire eratostene.out va conţine pe prima linie numărul C, reprezentând numărul valorilor citite care erau numere prime.

Restricţii şi precizări

• 1 ≤ n ≤ 1.000.000

Exemplu

eratostene.in

6
12 18 19 25 29 7

eratostene.out

3

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

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

bool c[1000005];

int main()
{
    c[0] = c[1] = 1;
    for(int i = 2; i <= 1000; ++i)
        if(c[i] == 0)
            for(int j = 2; i * j <= 1000000; ++j)
                c[i * j] = 1;

    int n;
    cin >> n;
    int x;
    int cnt = 0;
    for(int i = 1; i <= n; ++i){
        cin >> x;
        if(c[x] == 0)
            cnt++;
    }

    cout << cnt;

    return 0;
}