Cod sursa(job #2679317)

Utilizator lucametehauDart 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;
}