Skip to content

Instantly share code, notes, and snippets.

@kimwalisch

kimwalisch/segmented_bit_sieve1.cpp

Last active March 6, 2018 13:36
Show Gist options
  • Save kimwalisch/77553c9dbd2e67e3961a722c9d23e958 to your computer and use it in GitHub Desktop.
Save kimwalisch/77553c9dbd2e67e3961a722c9d23e958 to your computer and use it in GitHub Desktop.
Download ZIP
Segmented bit sieving
Raw
segmented_bit_sieve1.cpp
// sieve segment using bit array
for (std::size_t i = 0; i < primes.size(); i++)
{
int64_t j = multiples[i];
for (int64_t k = primes[i] * 2; j < segment_size; j += k)
sieve[j >> 4] &= unset_bit[j & 15];
multiples[i] = j - segment_size;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment