Cod sursa(job #2499970)
Utilizator | Radu Stancu radustn92 | Data | 27 noiembrie 2019 00:32:39 |
---|---|---|---|
Problema | Ciurul lui Eratosthenes | Scor | 70 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.47 kb |
#include <cstdio>
#include <bitset>
#include <vector>
using namespace std;
const int NMAX = 2000505;
int N, lp[NMAX];
vector<int> pr;
int main() {
freopen("ciur.in", "r", stdin);
freopen("ciur.out", "w", stdout);
scanf("%d", &N);
for (int i = 2; i <= N; i++) {
if (lp[i] == 0) {
lp[i] = i;
pr.push_back(i);
}
for (int j = 0; j < pr.size() && pr[j] <= lp[i] && i * pr[j] <= N; j++) {
lp[i * pr[j]] = pr[j];
}
}
printf("%d\n", (int) pr.size());
return 0;
}