Criba de Erathostenes

[isaac]

Aqui les va un código de la Criba de Erathostenes bastante eficiente y que ahorra memoria.

Code: Select all

const int LIM = 100000000;

bool take[(LIM + 2) >> 1];
bool prime[LIM / 20], cp=0;

void criba() {

       for(int i=3;i*i <= LIM;i+=2)
            if(!take[i >> 1])
                for(int j = i*i;j <= LIM;j += (i << 1))
                      take[j >> 1] = true;

       prime[cp++] = 2;

       for(int i=3;i<=LIM;i+=2)
            if(!take[i >> 1])
                prime[cp++] = i;

}