Cod sursa(job #626911)

Utilizator Smaug-Andrei C. Smaug- Data 28 octombrie 2011 16:43:32
Problema Ciurul lui Eratosthenes Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.45 kb
Raporteaza aceasta sursa 
#include <cstdio>

#define MAXN 2000100>>4

int main(){
  
  freopen("ciur.in", "r", stdin);
  freopen("ciur.out", "w", stdout);

  static char P[MAXN];

  int i, j, cnt=1, N;

  scanf("%d", &N);
  
  for(i=1; ((i*i)<<1)+(i<<1) <= N; i++)
    if(!(P[i>>3] & (1<<(i&7))))
      for(j=((i*i)<<1)+(i<<1); (j<<1)+1 <= N; j+=(i<<1)+1)
	P[j>>3] |= (1<<(j&7));
   
  for(i=1; (i<<1)+1 <= N; i++)
    if(!(P[i>>3] & (1<<(i&7))))
      cnt++;

  printf("%d\n", cnt);

}