Cod sursa(job #1139085)
Utilizator | Bogdan Sitaru bogdan10bos | Data | 10 martie 2014 21:03:59 |
---|---|---|---|
Problema | Ciurul lui Eratosthenes | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
#include <cstdio>
using namespace std;
int i, j, nr, n;
char v[150007];
int main()
{
freopen("ciur.in", "r", stdin);
freopen("ciur.out", "w", stdout);
scanf("%d", &n);
nr=1;
for(i=1;((i*i) << 1)+(i << 1)<=n;i++)
if((v[i>>3]&(1<<(i&7)))==0)
{
for(j=((i*i)<<1)+(i<<1);(j<<1)+1<=n;j+=(i<<1)+1)
v[j>>3] |= (1<<(j&7));
}
for(i=1;(i<<1)+1<=n;i++)
if((v[i>>3]&(1<<(i&7)))==0)
nr++;
printf("%d", nr);
return 0;
}