Cod sursa(job #2679317)
Utilizator | Dart Monkey lucametehau | Data | 30 noiembrie 2020 11:49:32 |
---|---|---|---|
Problema | Ciurul lui Eratosthenes | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.51 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream in ("ciur.in");
ofstream out ("ciur.out");
int cnt, n, m;
unsigned viz[62505];
int primes[200005];
int main() {
in >> n;
for(int i = 2; i <= n; i++) {
if(!(viz[i >> 5] & (1 << (i & 31)))) {
primes[++m] = i;
}
for(int j = 1; j <= m && i * primes[j] <= n; j++) {
int nr = i * primes[j];
viz[nr >> 5] |= (1 << (nr & 31));
if(i % primes[j] == 0)
break;
}
}
out << m;
return 0;
}