A faster "buildX(u32 m)". Odd multiples of 3 are written with three 32-bits words in "x", starting at x[1], a simple solution for the first word: x[0] = 0x9b4b3491; In a similar way the next prime(s) 5,7.. could be marked, but with deminishing returns. /* old-ns-new old-s-new primes < 25 47 47 p < 2^31 7.4 7.1 < 50 62 62 < 2^32 15.8 15.2 < 100 109 94 < 200 187 156 < 400 312 250 < 800 578 436 < 1600 1092 843 < 3200 2152 1700 < 6400 4274 3385 */ void buildX(u32 m) // mark odd composites { m -= m / ~0u; m += m & 1; m >>= 1; u32 a = 1, b = 2, c = 3, d = m >> 5; x.resize(d + 1); x[0] = 0x9b4b3491; for (; a <= d; a += 3) x[a] = 0x24924924; for (; b <= d; b += 3) x[b] = 0x49249249; for (; c <= d; c += 3) x[c] = 0x92492492; for (a = 5, b = 12, c = 8; b < m; a += 2, b += c += 4) if ((x[a >> 6] & 1 << (a >> 1)) == 0) for (d = b; d < m; d += a) x[d >> 5] |= 1 << d; x[m >> 5] |= ~0u << m; } Latest version: https://pastebin.com/JMdTxbeJ Primes < 2^32 in 4.2 seconds.