pe77.cpp

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;
            }
        }
    }