Find the sum of prime numbers below 2 million

Question

This code is trying to find the sum of prime numbers below 2 million. The code does work as intended, but it takes a very long time ( 6 minutes) for the code to execute completely. What is the problem and how can I make it more efficient?

#include <iostream>
using namespace std;

unsigned long summationOfPrime();
bool isPrime(int n);
int main() {

cout <<summationOfPrime() << endl;

}

unsigned long summationOfPrime()
{
const int num = 2000000;
unsigned long sum = 0;
for(int i = 2; i < num; i++)
{
    if(isPrime(i) == true)
    {
        sum += i;

    }
}

return sum;
}

bool isPrime(int n)
 {
// Corner case
if (n <= 1)
    return false;

// Check from 2 to n-1
for (int i = 2; i < n; i++)
    if (n % i == 0)
        return false;

return true;
}

Answer 1

There are several issues, but here goes. Firstly, your indentation is all wonky. Some of this may be due to trying to input stuff here, but either way, indentation helps legibility.

Next, the biggest thing you can change to speed thing up is to replace for (int i = 2; i < n; i++) with for (int i = 2; i*i <= n; i++). This works because if \$a \cdot b = n\$, one of them is at most the square root of \$n\$. This change will probably make your code fast enough on its own.

That said, the much better solution to this type of problem is to use a prime sieve such as the Sieve of Eratosthenes which will generate all of the primes less than 1,000,000 faster by using addition and multiplication instead of modulo operations which are slower.

Answer 2

Don’t write using namespace std;.

You can, however, in a CPP file (not H file) or inside a function put individual using std::string; etc. (See SF.7.)

---

unsigned long summationOfPrime();
bool isPrime(int n);
int main() {

Put main last, so you don’t have to forward-declare your functions.

---

unsigned long summationOfPrime()
{
    const int num = 2000000;

You can use separators in numbers for readability now. And, good practice is to define these as constexpr. So:

    constexpr auto num = 2'000'000;

---

    for (int i = 2; i < num; i++)   {

Performance suggestions: see next section

---

        if (isPrime(i) == true)

You know isPrime already returns a bool. You do not need to check that against true again. In fact, it’s rather silly.

---

You do not have to write that loop at all, if you use std algorithms. accumulate sums the values, but generating the list of primes might be a bit tricky. But you do want to keep a list of all the primes! See below.

Performance

    if (n % i == 0)

Modulo is very slow and jams up the CPU so it is even slower than you would think! Minimizing the number of tests will give you big benefits.

When you test isPrime, you test every odd number less than n. You only need to test prime numbers up to √n, which is much fewer! So, note each found prime in a vector, and have isPrime consult the list thus far to do its job!

for ( ⋯ 
    prune down candidates  (see next note)
    if (isPrime(n))  {
        primes.push_back(n);
        sum += n;
    }
}

bool isPrime (int n)
{
    for (auto d : primes) {
        // rely on compiler realizing that simultaneous div and mod is one op
        const auto quo = n / d;
        const auto rem = n % d;
        if (rem == 0)  return false;
        if (quo <= d)  return true;  // I can quit now!
    }
    throw std::logic_error ("should not happen");
}

Think about what happens if (say) 27 is divided by 5. You get 5 plus remainder 2. You do not have to check any numbers greater than 5, because if anything succeeded you would have found it earlier. I just threw that together — you should check the edge cases, e.g. <= vs just <, or what if you have a perfect square.

---

To generate the candidates, you intuitively knew that you only need to check the odd numbers. But you can rule out many more than that! Consider that numbers ending in 5 are also not prime. Look at a grid where you blocked out primes and you will find a simple pattern: A prime must be one less than or one greater than a multiple of 6.

So, count by sixes, and try the value on either side.

  unsigned long sum= 2+3+5+7;  // special case.  Avoid adding 2 and 5 to primes list, since I avoid them here.
  primes.push_back(3);
  for (int step= 12;  step < num;  step+=6)
  {
      check (step-1);
      check (step+1);
  }

Again, look for the edge cases: what if num is a multiple of 6? And don’t test num+1 !

---

I hope that gives you food for thought! Your current algorithm is Order of n squared. By stopping the search early it will be order of n to the 1.5 power. Then reducing the number of tests to about the log of what you were doing will bring it down to n∙log(√n) which is better than n∙log(n).

IOW, the difference will be spectacular.

Answer 3

Your implementation to calculate if you have a prime is very problematic from a performance point of view as you even call it in a loop.

For this kind of usage, it would be much more efficient to calculate all the primes up to your count before processing. A possible implementation could be:

#include <vector>

namespace
{
    bool isPrime(const std::vector<int> &prevPrimes, int i)
    {
        for (auto prime : prevPrimes)
            if ((i % prime) == 0)
                return false;
        return true;
    }

    std::vector<int> getPrimesUntil(int max)
    {
        if (max <= 1)
            return {};

        auto primes = std::vector<int>{};
        for (int i = 2; i < max; ++i)
            if (isPrime(primes, i))
                primes.push_back(i);
        return primes;
    }

}

Answer 4

As others have said you can stop at i*i <= num

Check for divisible by 2
Then you can start at 3 and += 2

This is C# but it runs in less than 3 seconds on my machine
10 million in 17 seconds

public static bool IsPrime(this int num)
{
    if(num < 2)
    {
        throw new ArgumentOutOfRangeException();
    }
    if(num <= 3)
    {
        return true;
    }
    if (num % 2 == 0)
    {
        return false;
    }
    for (int divisor = 3; divisor * divisor <= num; divisor += 2)
    {
        if (num % divisor == 0)
        {
            return false;
        }
    }
    return true;
}

Can even increment by 6 and only test 1/3 of the numbers

public static bool IsPrime6(this int num)
{
    if(num < 2)
    {
        throw new ArgumentOutOfRangeException();
    }
    if(num <= 3)
    {
        return true;
    }
    if (num % 2 == 0)
    {
        return false;
    }
    if (num % 3 == 0)
    {
        return false;
    }
    for (int divisor = 5; divisor * divisor <= num; divisor += 6)
    {
        if (num % divisor == 0)
        {
            return false;
        }
        if (num % (divisor+2) == 0)
        {
            return false;
        }
    }
    return true;
}