Skip to content

Instantly share code, notes, and snippets.

@grantmwilliams
Last active April 14, 2016 05:10
Show Gist options
  • Save grantmwilliams/c8b7a33579a537ca36b0a385d7f93f26 to your computer and use it in GitHub Desktop.
Save grantmwilliams/c8b7a33579a537ca36b0a385d7f93f26 to your computer and use it in GitHub Desktop.
std::vector<int> get_primes(int limit)
{
std::vector<char> primes(limit, 1);
std::vector<int> final;
// 0 and 1 are nonprime by definition
primes[0] = 0; primes[1] = 0;
for (int i = 2; i * i <= limit; i++)
{
if(primes[i])
{
// pushes back any prime below sqrt(limit)
final.push_back(i);
for (int j = i * i; j <= limit; j+= i)
{
primes[j] = 0;
}
}
}
// now we loop over all primes we've found over sqrt(limit)
for (int k = (int)floor(sqrt((limit))) + 1; k <= limit; k++ )
{
if(primes[k])
{
final.push_back(k);
}
}
return final;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment