Criba de Erathostenes

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
Post Reply
User avatar
Posts: 83
Joined: 3 years ago
Gender: None specified

Criba de Erathostenes

Post by isaac » 3 years ago

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;


Post Reply

Return to “Algorithms”