This question is (also) a CodeEval problem named Sum of Primes.
Even though it looks similar to the previous CodeEval problem I have seen, there's something that makes it more interesting:
int solution()
{
std::vector<int> primes; // 1
primes.reserve(1000);
primes.push_back(2);
primes.push_back(3);
for(int i = 5; primes.size() < 1000; i+=2) // 2
{
bool isPrime = true;
for(unsigned j = 1; j < primes.size() && (std::pow(primes[j], 2) <= i); ++j) // 3
{
if(i % primes[j] == 0)
{
isPrime = false;
break;
}
}
if(isPrime)
primes.push_back(i);
}
return std::accumulate(primes.begin(), primes.end(), 0); // 4
}
1. I am going to put the generated primes in this vector.2. I have already pushed the first two elements by hands, now I push all the other ones. I start checking 5, and then I step to the next odd number.
3. To check if a number is prime, it is enough to ensure that no other prime number is among its divisors. Moreover, we can stop checking when we reach a tentative divisor that, when squared, is bigger than the candidate prime.
4. Finally, just sum all the prime numbers up.
Some time ago, I have written about a similar but more general problem, how to check if a given number is prime.
No comments:
Post a Comment