Skip to content

Instantly share code, notes, and snippets.

@grantmwilliams
Last active April 14, 2016 06:45
Show Gist options
  • Save grantmwilliams/fbeb7329f90259971237593305ea6c2a to your computer and use it in GitHub Desktop.
Save grantmwilliams/fbeb7329f90259971237593305ea6c2a to your computer and use it in GitHub Desktop.
std::vector<int> get_primes(int limit)
{
std::vector<char> primes(limit + 1, 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 starting from sqrt(limit) + 1
for (int k = (int)floor(sqrt((limit))) + 1; k <= limit; k++ )
{
if(primes[k])
{
final.push_back(k);
}
}
return final;
}
void prime_sums(int limit)
{
// guess the range of primes to try so we can sieve
int prime_num_guess = 100;
// start by getting our primes
std::vector<int> primes = get_primes(prime_num_guess);
int size = prime_num_guess; // magic number...
int tmp[size] = {1};
for (auto p:primes)
{
for (int i = 0; i + p <= size; i++)
{
tmp[i + p] += tmp[i];
}
}
for (int j = 0; j < size; j++)
{
if (tmp[j] > limit)
{
std::cout << "The first number that can be written as the sum of primes in over " << limit << " ways is: " << j << "\n";
return;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment