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