Cod sursa(job #1946327)
Utilizator | Geman Dorin Andrei dorin31 | Data | 30 martie 2017 08:09:31 |
---|---|---|---|
Problema | Ciurul lui Eratosthenes | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.5 kb |
#include <iostream>
#include <fstream>
#include <bitset>
#define maxN 200000002
#define int64 long long
using namespace std;
ifstream fin("ciur.in");
ofstream fout("ciur.out");
bitset <maxN/2> ciur;
int n,k;
void buildCiur()
{
if (n>=2) ++k;
for (int i=3; i<=n; i+=2)
if (!ciur[i>>1])
{
++k;
for (int64 j=1LL*i*i; j<=n; j+=i<<1)
ciur[j>>1]=1;
}
}
int main()
{
fin>>n;
buildCiur();
fout<<k;
return 0;
}