Pagini recente » Cod sursa (job #232187) | Cod sursa (job #367525) | Cod sursa (job #2671370) | Cod sursa (job #592100) | Cod sursa (job #2879591)
#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;
}