Cod sursa(job #1908601)
| Utilizator | Data | 7 martie 2017 09:36:54 | |
|---|---|---|---|
| Problema | Ciurul lui Eratosthenes | Scor | 10 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.61 kb |
#include <fstream>
#include <bitset>
#define in "ciur.in"
#define out "ciur.out"
#define N 2000003
using namespace std;
ifstream fin(in);
ofstream fout(out);
bitset<N> f;
int n;
void Ciur(int n)
{
f[0] = f[1] = 1;
for(int i=4; i<=n; i+=2)
f[i] = 1;
for(int i=3; i*i<=n; i+=2)
if(!f[i])
for(int d=i*i; d<=n; d += 2*i) f[i] = 1;
}
int Solve()
{
int rez = 0;
for(int i=2; i<=n; ++i)
if(!f[i]) ++rez;
return rez;
}
int main()
{
fin>>n;
Ciur(n);
fout<<Solve();
fin.close(); fout.close();
return 0;
}
