Skip to content

Instantly share code, notes, and snippets.

@kimwalisch
Last active March 6, 2018 13:35
Show Gist options
  • Save kimwalisch/df7dddbb1676969cb08e9c495181384a to your computer and use it in GitHub Desktop.
Save kimwalisch/df7dddbb1676969cb08e9c495181384a to your computer and use it in GitHub Desktop.
Segmented sieve
// sieve the current segment
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] = false;
multiples[i] = j - segment_size;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment