Find the sum of all prime numbers below N

This is another classic question. Everyone would immediately come up with an idea that we can iterate from 2 to N and check if it is a prime number. If so, we add it to the sum.

bool isprime(int num) {
    int j = sqrt((float)num);
    for(int i = 2; i <= j; i++) {
        if(num % i == 0)
            return false;
    }
    return true;
}

int primesum(int range) {
    int sum = 2;
    for(int i = 3; i <= range; i += 2) {
        if(isprime(i))
            sum += i;
    }
    return sum;
}

This solution uses Trail Division to test if a number is prime. The trial factors need go no further than sqrt(n) because, if n is divisible by some number p, then n = p * q and if q were smaller than p, n would have earlier been detected as being divisible by q or a prime factor of q. 

When calculating the sum, we only need to check even numbers. This would save half of the time.

The time complexity of this method is O(n * sqrt(n)), and it requires O(1) space. The algorithm can be further optimized if we have a smaller pre-generated prime number table and test only prime factors.


If extra space is allowed, there is a better solution which is called Seive of Eratosthenes. The basic idea is to directly generate composite numbers rather than testing for prime numbers. The Seive of Eratosthenes algorithm is described as follows:

1. Create a list of consecutive integers from 2 to n: (2, 3, 4, ..., n).
2. Initially, let p equal 2, the first prime number.
3. Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked.
4. Find the first number greater than p in the list that is not marked; let p now equal this number (which is the next prime).
5. If there were no more unmarked numbers in the list, stop. Otherwise, repeat from step 3.

When the algorithm terminates, all the numbers in the list that are not marked are prime.

int primesum(int range) {
    int sum = 2;
    bool* prime_table = new bool[range];
    memset(prime_table, true, sizeof(bool));

    for(int i = 2; i <= range / 2; i++) {
        if(prime_table[i]) {
            for(int j = 2 * i; j <= range; j += i) {
                prime_table[j] = false;
            }
        }
    }
    for(int i = 3; i <= range; i += 2) {
        if(prime_table[i])
            sum += i;
    }
    return sum;
}

The time complexity is O(nloglogn), and space complexity if O(n).

Above is only the implementation of original version. There are some refinements of this algorithm. For further informaton, please go to this link http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.