retine in coada doar cotele care urmeaza sa se topeasca in urmatoarea zi.

nu trebuia de scos testul de la oni.

 
buna! va scrie un pasionat de informatica din R.Moldova.
M-am apucat de informatica la 27 de ani si acum sunt student (am 29 de ani) la Universitatea Tehnica din Moldova. Referitor la articolul "operatii pe biti... ciurul lui Eratostene"- care de ltfel e un articol destul de interesant! Daca nu gresesc asi vrea sa fac unele corectii ale codului, si anume:
#define maxsize 10000000
02.
03.char at[maxsize / 16];
04.int n;
05.
06.int isPrime(int x) {
07.if (!(x & 1))
08.if (x == 2) return 0 ;
09.else return 1 ;
10.else return (at[((x - 3) >> 1) >> 8] & (1 << (((x - 3) >> 1) & 7))) ;
11.}
12.
13.void sieve() {
14.int i, j;
15.memset(at, 0, sizeof(at)) ;
16.for (i = 3; i <= maxsize; i += 2)
17.if (!at[((i - 3) >> 1) >> 8] & (1 << (((i - 3) >> 1) & 7)))
18.for (j = i * i ; j <= maxsize ; j += i + i)
19.at[((i - 3) >> 1) >> 8] |= (1 << (((i - 3) >> 1) & 7))) ;
20.}

in sectiunea 17 in loc de if (!at[((i - 3) >> 1) >> 8] & (1 << (((i - 3) >> 1) & 7)))
ar trebui de scris if (!(at[((i - 3) >> 1) >> 3] & (1 << (((i - 3) >> 1) & 7))))
sau chiar if 17.if (!(at[i  >> 4] & (1 << ((i  >> 1) & 7))))
astfel evitându-se scăderea repetată (x-3) dar cu prețul pierderii primilor trei biți din primul octet
al char-ului at[], astfel fiind necesar de a rezerva cu un octet mai multă memorie decât este necesar.
A doua observație ar fi ca în secțiunea   19.at[((i - 3) >> 1) >> 8] |= (1 << (((i - 3) >> 1) & 7))) ;
la fel aceiași observație , plus că în loc de i trebuie să fie j, adică:
19.at[((j-3) >> 1) >> 3] |= (1 << (((j - 3) >> 1) & 7))) ;
sau cum am mai spus mai sus :19.if (!(at[j  >> 4] & (1 << ((j  >> 1) & 7))))
O a treia observație ar fi cea din funcția :
int isPrime(int x) {
07.if (!(x & 1))
08.if (x == 2) return 0 ;
09.else return 1 ;
10.else return (at[((x - 3) >> 1) >> 8] & (1 << (((x - 3) >> 1) & 7))) ;
11.}
și anume :
int isPrime(int x) {
07.if (!(x & 1))
08.if (x == 2) return 1 ;
09.else return 0 ;
10.else return ( ! (at[((x - 3) >> 1) >> 8] & (1 << (((x - 3) >> 1) & 7))) );
11.}

Codul final ar fi:
#include <stdio.h>
#include <memory.h>
#include <conio.h>

#define maxsize 30000

char sita[maxsize / 16 + 1];
int n;

int isPrime(int );
void sieve();

int main()
{
     clrscr();
     sieve();
     printf("\n n= "); scanf("%d", &n);
     for (int i=3; i <= n; i+=2)
   if (isPrime(i)) printf("%d este prim\n", i);
      else printf("%d nu este prim\n", i);
    getch();
    return 0;
}

int isPrime(int x)
{
    if (x <= 1) return 0;
    if (!(x & 1))
       if (x == 2) return 1;
     else     return 0;
       else return ( !(sita[x >> 4] & (1 << ((x >> 1) & 7))) );
}

void sieve()
{
   int i, j;
   memset(sita, 0, sizeof(sita));
   for (i=3; i * i <= maxsize; i+=2)
      if ( !(sita[i >> 4] & (1 << ((i >> 1) & 7))) )
    for (j=i * i; j <= maxsize; j+=i + i)
         sita[j >> 4] |= (1 << ((j >> 1) & 7));
}

De altfel ași vrea să vă mulțumesc pentru acest articol și pentru multe altele, de fapt faceți o treabă foarte bună. Am analizat acestă sursă o zi întreagă și credeți-mă că am avut ce învăța, mai ales subtilitățile -  for (j=i * i; j <= maxsize; j+=i + i). Mult succes în continuare!