Cod sursa(job #355888)

Utilizator DEYDEY2Tudorica Andrei DEYDEY2 Data 12 octombrie 2009 15:42:24
Problema Ciurul lui Eratosthenes Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<fstream.h>
unsigned char x[50000];

unsigned long dabit(long n)//returneaza bit-ul corespunzator numarului n
{
  unsigned char c=x[1+(n-1)/8];
  int i;
  for(i=1;i<1+(n-1)%8;i++)c=c/2;
  return c%2;
}

void punebit(long n)//pune bit-ul corespunzator numarului n pe valoarea 1
{
  //in x["octet"], pe pozitia "bit" pun valoarea 1
  long octet=1+(n-1)/8;
  int bit=1+(n-1)%8,i;
  unsigned char doi=1;//calcul masca=peste tot 0, doar pozitia "bit"=1
  for(i=1;i<bit;i++)doi=doi*2;
  x[octet]=x[octet]|doi;//sau logic la nivel de bit
}

void afis(unsigned char c)
{
  int i;
  for(i=0;i<=7;i++){cout<<c%2;c=c/2;}
  cout<<endl;
}

void main()
{
  ifstream f("ciur.in");
  ofstream g("ciur.out");
  unsigned long n,i,j;
  f>>n;
  for(i=1;i<=n;i++)x[i]=0;
  for(i=2;i<=n/2;i++)
    if(dabit(i)==0)
      for(j=2*i;j<=n;j=j+i)
	punebit(j);
  for(i=2;i<=n;i++)
    if(dabit(i)==0)g<<i<<endl;
  f.close();
  g.close();
}