Sum of all primes under 2 million

Question

I have this assignment to write the optimized space and time code for finding the sum of all primes under 2 million. I'm using the following function to check if each number is prime:

int IsPrime(unsigned int number) {
    if (number <= 1) return 0; 
    unsigned int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

And running a for loop from 1 to 2 million using a long double, and checking each number if it is prime and then adding it. Is there a more optimized method to do this?

Answer 1

There are dozens of possible optimizations. The most obvious -- why are you multiplying i by itself every pass in the loop?! Just calculate the loop cut off once.

And why i++?! After you test 2, there's no reason to test 4, 6, or 8. You can test 2, and then start from 3 adding 2 each time instead of one.

Also, since you need to find all the primes up to a given point, you should be using a sieve rather than testing each number.

Answer 2

To enumerate all prime number below a limit you could use Sieve of Eratosthenes as mentioned by @David Schwartz in the comment:

#include <cmath>
#include <iostream>
#include <vector>
#include <stdint.h>

namespace {
  // yield all prime numbers less than limit.
  template<class UnaryFunction>
  void primesupto(int limit, UnaryFunction yield)
  {
    std::vector<bool> is_prime(limit, true);

    const int sqrt_limit = std::sqrt(limit);
    for (int n = 2; n <= sqrt_limit; ++n)
      if (is_prime[n]) {
        yield(n);    
        for (unsigned k = n*n, ulim = limit; k < ulim; k += n)
          //NOTE: "unsigned" is used to avoid an overflow in `k+=n`
          //for `limit` near INT_MAX
          is_prime[k] = false;
      }

    for (int n = sqrt_limit + 1; n < limit; ++n)
      if (is_prime[n])
        yield(n);
  }
}

int main() {
  uintmax_t sum = 0;
  primesupto(2000000, [&sum] (int prime) { sum += prime; });
  std::cout << sum << std::endl;
}

Demo

$ g++ -std=c++0x sum-primes.cc -o sum-primes && ./sum-primes
142913828922

Answer 3

I have done that before. The point is that you don't have to divide your number by all odd numbers smaller than it, but by all PRIME numbers smaller than it.

So, pass the list of the prime numbers you had found to the function and divide your new number by each them.

Answer 4

Your IsPrime function looks OK. This won't help it's speed very much, but it will a little...

bool isPrime(unsigned int number) {
   if (number <= 1) {
      return false;
   } else if (number % 2 == 0) {
      return number == 2;
   } else {
      for (unsigned int i = 3; true; i += 2) {
         const unsigned int remainder = number % i;
         const unsigned int quotient  = number / i;
         if (remainder == 0) {
            return false;
         } else if (quotient < i) {
            return true;
         }
      }
   }
}

This takes about half the time because some processors (all x86 processors) have a combined 'find the remainder and quotient' instruction that this leverages. It also avoids testing even numbers. If your number is not divisible by 2, it won't be divisible by any other even number other, since all even numbers can also be divided by 2.

Also, make sure you have compiler optimizations turned on.

This is basically like hard-coding the very first step of the Sieve of Eratosthenes. Using the full sieve is likely a lot slower. But using the first step like this and hard-coding it as a step-distance will be much faster.

Answer 5

For every prime number n>=5, n mod 6 returns 1 or n mod 6 returns 5. If you check these candidates for primeness by seeing if any prime number that is less than or equal to sqrt(n) divides a candidate could help eliminate many checks. When you do find a prime number, you could add to a list or, just add up to get the sum. The thing about this method is, it helps eliminate many checks that would simply return composite instead of prime, which is what you are looking for.

Answer 6

As others have pointed out, you can cut your work in half by avoiding even numbers. However, avoiding even numbers after 2 is just the first part of using a sieve: if you filter by every prime number found up to the square root of a particular number that you want to test, you can check by only those numbers.

Here is some java-like psuedocode to illustrate what I'm saying:

public List findPrime(int upperLimit){
    List primes = new List();
    primes.add(2);
    for(int i=3;i<upperLimit;i++){
        boolean primeFlag = true;
        for(test in primes){
            if(test > sqrt(i)
                break;
            if(i % test == 0){
                primeFlag = false; break;
            }
        }
        if(primeFlag) primes.add(i);
     }
}