10
\$\begingroup\$

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;
}
\$\endgroup\$
17
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Can you explain a little bit more on the i*i <= n part? \$\endgroup\$ – austingae Jun 2 '18 at 17:57
  • \$\begingroup\$ since either a or b is less than sqrt n, then to see if a number has prime factors, you only need to find the minimum factor, so you only need factors i st. i*i<=n \$\endgroup\$ – Oscar Smith Jun 2 '18 at 19:41
  • 2
    \$\begingroup\$ Suggestion: calculate the square root of n once before the loop and use that instead of calculating i*i for every iteration of i. Might be insignificant, but for large numbers, it might help \$\endgroup\$ – userSeventeen Jun 3 '18 at 15:48
  • \$\begingroup\$ that would be slightly better, but rather than chasing a few percent here and there like that, you should just switch to a sieve. \$\endgroup\$ – Oscar Smith Jun 3 '18 at 17:15
  • 1
    \$\begingroup\$ @Bent The article you linked shows some improvements to a naive algorithm and ends with a still too naive and slow one. Ditch it. While SoE does some work "over and over", the number of times this happens is equal to the number of distinct prime divisors, so it's usually pretty low. I'd bet any amount it wins by an order of magnitude. \$\endgroup\$ – maaartinus Jun 3 '18 at 23:48
10
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ it will be order of n to the 1.5 power. citation please. \$\endgroup\$ – Rishav Jun 2 '18 at 22:44
  • \$\begingroup\$ Also, $\mathcal O(n \log n) = \mathcal O(n \log \sqrt n)$, so how is that better? \$\endgroup\$ – AlexR Jun 3 '18 at 8:41
  • \$\begingroup\$ @Rishav I think that‘s correct: WolframAlpha \$\endgroup\$ – AlexR Jun 3 '18 at 8:46
  • \$\begingroup\$ @Rishav The number of iterations of the search loop goes to √n as explained at the top: no sense in searching farther! You run the search loop n times. \$\endgroup\$ – JDługosz Jun 3 '18 at 22:38
  • 1
    \$\begingroup\$ @JDługosz Still n log(sqrt(n)) = 1/2 n log n is just a constant factor, right? And the faster cancellations happen in the worse algorithm as well, no? \$\endgroup\$ – AlexR Jun 4 '18 at 5:10
1
\$\begingroup\$

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;
    }

}
\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.