Cod sursa(job #2879591)

Utilizator QwertyDvorakQwerty Dvorak QwertyDvorak Data 28 martie 2022 19:25:07
Problema Ciurul lui Eratosthenes Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define dbg(x) cout << #x <<": " << x << "\n";
#define sz(x) ((int)x.size())

using ll = long long;

const string fn = "ciur";
ifstream fin(fn + ".in");
ofstream fout(fn + ".out");

// vector<int> primes;

const int mxPrime = 200000;
bitset<mxPrime + 5> prime;

void sieve(){

	prime[0] = prime[1] = 1;
	for (int i = 4; i <= mxPrime; i += 2)
		prime[i] = 1;

	for (int i = 3; i * i <= mxPrime; i += 2)
		if(prime[i] == 0)
			for (int j = i * i; j <= mxPrime; j += i + i)
				prime[j] = 1;
	prime.flip();

	// for (int i = 2; i <= mxPrime; ++i)
	// 	if(prime[i])
	// 		primes.push_back(i);
}


int main(){

	int x;
	fin >> x;
	sieve();
	int ans = 0;
	for (int i = 1; i <= x; ++i)
		ans += prime[i];
	fout << ans << '\n';
	return 0;
}