Cod sursa(job #1122305)
Utilizator | Andrei Stoica delta_wolf | Data | 25 februarie 2014 17:28:38 |
---|---|---|---|
Problema | Ciurul lui Eratosthenes | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.48 kb |
#include <cstdio>
using namespace std;
int n,i,nr,j;
char p[2000010/2/8+1];
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((p[i>>3]&(1<<(i&7)))==0)
for(j=((i*i)<<1)+(i<<1);(j<<1)+1<=n;j+=(i<<1)+1)
p[i>>3]|=(1<<(i&7));
}
for(i=1;(i<<1)+1<=n;i++)
if((p[i>>3]&(1<<(i&7)))==0)
nr++;
printf("%d",nr);
return 0;
}