Problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

one of my fav problems, learned a lot of stuff from it.

Implementation using sieve of Eratosthenes ::

#include <iostream>
#include <vector>

using namespace std;

int main()
{
        unsigned const n = 10000000;  //value of n as per requirement
        vector<bool> p(n, true);
        long long int sum = 0;

        // sieve of Eratosthenes
        for(unsigned i = 2; i*i <= n; ++i)
                for(unsigned j = 2*i; j < n; j += i)
                        p[j] = false;

        // find m-th prime
        unsigned i = 2;
        for(unsigned c = 0; i !=2000000 ; ++i){
                if(p[i]) sum+=i;
        }

        cout<<sum<<endl;

        return 0;
}

Implementation using Sieve of Atkins::

/*
 *  Adaptation of the Sieve of Atkin (faster than the Sieve of Eratosthenes), but using modulo-thirty.
 *  The idea is:
 *  - 30 is the lcm of 2, 3 and 5 (the first 3 primes);
 *  - get the list of 30 next numbers (1..30, 31..60, etc) and discard all multiples of 2, 3 and 5;
 *  - it will remain 1, 7, 11, 13, 17, 19, 23 and 29
 *  - so, you only have to test the numbers in this groups.
 *
 *   good ref. --> http://www.codeproject.com/KB/recipes/PrimeSuspect.aspx
 *      
 */


#include <iostream>
#include <stdbool.h>
#include <math.h>
#include<cstdio>
#include<vector>
#define ulli unsigned long long int

using namespace std;

bool prime(ulli n, vector<unsigned long long int> &vec) {
    int i;
    ulli max = (ulli)sqrt((ulli)n);
    for (i = 0; vec[i] <= max; i++)
        if (n % vec[i] == 0)
            return (false);
    return (true);
}

#define prime_test if (prime(num,primes)) primes[++i] = num
int main()
{
    int i = 9;
    ulli num = 31;
    vector<ulli> primes(200001);
    primes[0]=2;primes[1]=3;primes[2]=5;primes[3]=7;primes[4]=11;primes[5]=13;primes[6]=17;primes[7]=19;primes[8]=23;primes[9]=29;
    while (i < 200000) {
        prime_test; // 1
        num+=6;
        prime_test; // 7
        num+=4;
        prime_test; // 11
        num+=2;
        prime_test; // 13
        num+=4;
        prime_test; // 17

        num+=2;
        prime_test; // 19
        num+=4;
        prime_test; // 23
        num+=6;
        prime_test; // 29
        num+=2;
    }
    long long int sum=0;
    int k=0;
    while(primes[k]<2000000){
        sum+=primes[k];
        k++;
    }
    printf("%llu\n",sum);
    return 0;
}
#undef prime_test
#undef ulli
Advertisements