Skip to content

Instantly share code, notes, and snippets.

@kimwalisch

kimwalisch/segmented_bit_sieve2.cpp

Last active March 6, 2018 10:06
Show Gist options
  • Save kimwalisch/4c0703e97f3594dcb9b9ed83e55852a4 to your computer and use it in GitHub Desktop.
Save kimwalisch/4c0703e97f3594dcb9b9ed83e55852a4 to your computer and use it in GitHub Desktop.
Download ZIP
Counting bits in the segmented sieve of Eratosthenes
Raw
segmented_bit_sieve2.cpp
// unset bits > limit
if (high == limit)
{
int64_t bits = 0xff << (limit % 16 + 1) / 2;
sieve[sieve_size - 1] &= ~bits;
}
// count primes
for (int64_t n = 0; n < sieve_size; n++)
count += popcnt[sieve[n]];
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment