Cod sursa(job #2569364)
Utilizator | Cretoiu Patricia PatriciaCretoiu | Data | 4 martie 2020 11:55:38 |
---|---|---|---|
Problema | Ciurul lui Eratosthenes | Scor | 20 |
Compilator | cpp-64 | Status | done |
Runda | r3capitusulare | Marime | 0.69 kb |
#include <fstream>
#include <bitset>
using namespace std;
ifstream in("ciur.in");
ofstream out("ciur.out");
const int N = 2e6 + 6;
bitset<N>ciur;
int main()
{
int n, ans;
in >> n;
ans = 2;
for(int i = 5; i <= n; i += 6)
{
if(ciur[i] == 0)
{
ans++;
for(int j = i * i; j <= n; j += 2 * i)
ciur[j] = 1;
}
if(ciur[i + 2] == 0)
{
ans++;
int nr = i + 2;
for(int j = nr * nr; j <= n; j += 2*nr)
ciur[j] = 1;
}
}
if(n == 2) out << 1;
else if(n < 5) out << 2;
else out << ans;
return 0;
}