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