Hi all, today I found a very intesting prime sieve when I coding spoj PAGAIN: https://github.com/zobayer1/SPOJ/blob/master/PAGAIN.cpp The sieve is very fast and save memory but I can't understand what this code working:
#define ifC(n) (flag[n>>6]&(1<<((n>>1)&31)))
#define isC(n) (flag[n>>6]|=(1<<((n>>1)&31)))
Can anyone help me prove it?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 173 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 160 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
Feature "is prime" saved in array of 32bit integer. Every integer contain info about 32 non-even number. In array flag: element with index (n / 64) check/set (ifC/isC) bit with index (n/2) mod 32.
Prime number may be non-even (exclude 2), than even number not saved in flag[]
Sorry my english, isn't native language.
Свойсто простоты числа сохраняется в массиве 32битных чисел. Каждый элемент массива содержит информацию о простоте 32 нечётных чисел (чётные все непростые, кроме 2).
Функция ifC/isC проверяет/устанавливает i-ый бит элемента j в массиве, где i = (n/2) mod 32, а j = n/64.
FIRST
what is first?
Aatr0x does not have any contest participation and he/she is blue. Bug???