Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/// snippet from
/// http://www.geeksforgeeks.org/sieve-of-eratosthenes/
///
std::vector<bool> SieveOfEratosthenes(unsigned long less)
{
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
vector<bool> prime(less + 1);
std::fill(begin(prime), end(prime), true);
for (unsigned long p = 2; p*p <= less; p++)
{
// If prime[p] is not changed, then it is a prime
if (prime[p] == true)
{
// Update all multiples of p
for (unsigned long i = p * 2; i <= less; i += p)
prime[i] = false;
}
}
return prime;
// Print all prime numbers
//for (unsigned long p = 2; p <= less; p++)
// if (prime[p] == true)
// cout << p << " ";
}
unsigned long get_nth_prime_with_basic_sieve(unsigned long n) {
unsigned long precompute_max_count = 100000;
do
{
if (precompute_max_count >= std::numeric_limits<unsigned long>::max())
break;
auto prime = SieveOfEratosthenes(precompute_max_count);
// how manay 'true' exist?
unsigned long primes_length = std::count(std::begin(prime) + 2, std::end(prime), true);
if (primes_length < n) {
precompute_max_count *= 2; // double the limit & try again
continue;
}
// get index nth true locates
unsigned long nth = 0;
// from prime[2] - (prime[0] and prime[1] are true, but not prime numbers),
// if n is equal to the summed up prime numbers, then return the location.
auto it = std::find_if(begin(prime) + 2, end(prime), [nth, n](bool e) mutable {
if (e) { // find the true elements
nth++; // and increment the count
if (nth == n) // and we found Nth number,
return true;
}
return false;
});
// get the value of found index points to.
auto d = std::distance(begin(prime), it);
return d;
} while (true);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.