The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.Question is from Project Euler Q10 , which is a very interesting website.
Find the sum of all the primes below two million.
My Solution is as below, which has performance:
time a.out
sum of Prime = 142913828922
0.090u 0.005s 0:00.09 100.0% 0+0k 0+0io 0pf+0w
int l_iCount = 2;
const int l_iMax = 2000000;
const int IS_PRIME = 0;
const int NOT_PRIME = 1;
int l_arIntegers[l_iMax];
//initialize and assume all to be prime
memset(l_arIntegers, 0, sizeof(l_arIntegers));
l_arIntegers[0] = NOT_PRIME; //for 1
l_arIntegers[1] = IS_PRIME; //for 2
long long l_iSumOfPrimes = 0;
while(l_iCount < l_iMax)
{
if(l_arIntegers[l_iCount - 1] == IS_PRIME)
{
for(int i = 2 * l_iCount; i < l_iMax; )
{
if(l_arIntegers[i - 1] != NOT_PRIME)
l_arIntegers[i - 1] = NOT_PRIME;
i += l_iCount;
}
//it is a prime
l_iSumOfPrimes += l_iCount;
std::cout << "found a Prime = " << l_iCount << std::endl;
}
l_iCount++;
}
std::cout << "sum of Prime = " << l_iSumOfPrimes << std::endl;
When I started to code the solution, I tried the normal check for a prime number, it was too slow to be acceptable. then I thought maybe it is faster to create an array of all integers to be checked as above, just having simple comparison and assignment to 1, without tons of mod (%) operations. And the execution result proved to be working.
I have checked the recommended solutions from Project Euler after solving it, my solution is very close to the optimal answer.
Here is my Project Euler Label:
No comments:
Post a Comment