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