Lien's blog

Prime sieve
By Lien, 11 years ago, In English

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?

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
11 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
  Vote: I like it -12 Vote: I do not like it

FIRST

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Aatr0x does not have any contest participation and he/she is blue. Bug???

→ Reply