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.
User avatar
Posts: 83
Joined: Mon Oct 26, 2015 6:20 pm
Gender: None specified

Criba de Erathostenes

Postby isaac » Wed Oct 28, 2015 1:20 pm

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;


Return to “Algorithms”

Who is online

Users browsing this forum: No registered users and 1 guest