Cod sursa(job #1976938)
Utilizator | Institutul de Arta Gastronomica blatul | Data | 4 mai 2017 16:49:14 |
---|---|---|---|
Problema | Ciurul lui Eratosthenes | Scor | 30 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.54 kb |
#include <bits/stdc++.h>
using namespace std;
#define NMAX 2000002
ifstream fin("ciur.in");
ofstream fout("ciur.out");
bitset<NMAX> marked;
int ciur(const int N) {
if (N <= 1)
return 0;
int primes = 1;
for (int i = 3; i <= N; i += 2) {
if (!marked[i]) {
primes++;
for (int j = i * i; j <= N; j += i)
marked[j] = 1;
}
}
return primes;
}
int main() {
int N;
fin >> N;
fout << ciur(N);
return 0;
}