276
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; }
Comentarii