## 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.
isaac
Posts: 83
Joined: Mon Oct 26, 2015 6:20 pm
Gender:

### Criba de Erathostenes

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;}`