Thursday, August 16, 2012

Calculate the sum of all the primes below two million


The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
Question is from Project Euler Q10 , which is a very interesting website.

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