Cod sursa(job #2153036)
Utilizator | Enache Adelina ade_tomi | Data | 5 martie 2018 22:06:37 |
---|---|---|---|
Problema | Ciurul lui Eratosthenes | Scor | 20 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.47 kb |
#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;
const int NMAX = 2000005;
bitset<NMAX> prim;
int main() {
int n;
ifstream cin ("ciur.in");
ofstream cout ("ciur.out");
cin >> n;
for (int i = 3; i * i <= n; i+= 2) {
if (prim[i]) {
continue;
}
for (int j = i * i; j <= n; j+= 2 * i) {
prim[i * j] = 1;
}
}
cout << (n + 1) / 2 - prim.count();
return 0;
}