### Jason Schulz

Shared publicly -A simple prime sieve. It uses a bitset to represent the integer range sans even values. So, the function that maps from bit index to value is...

The seemingly bizarre

It's space efficient and reasonably fast. At first glance both clang and gcc don't seem to optimize the bitscans into

*f(x) = 2x + 1*The seemingly bizarre

*(3 *p) + 1*just multiplies the actual value by 3, and*(2 * p) + 1*similarly multiplies the value by 2.*size_t n = std::strtoull(argv[1], NULL, 10);**boost::dynamic_bitset<> cs((n + 1) / 2);**cs.set();**cs.set(0, false);**for (size_t p = 1; p != cs.npos; p = cs.find_next(p))**for (size_t c = (3 * p) + 1; c < cs.size(); c += (2 * p) + 1)**cs.set(c, false);**std::cout << cs.count() + 1 << std::endl;*It's space efficient and reasonably fast. At first glance both clang and gcc don't seem to optimize the bitscans into

*bsf*, which I don't fully understand though.1

Add a comment...