Project Euler #10 in C++ (sum of all primes below two million)

Question

Project Euler Problem 10 asks for the sum of all the primes below two million.

I'm creating a list of primes and keep checking any new number for divisibility with only prime numbers. I thought it should take less time but it is going over 4 minutes. How should I approach such a problem?

#include<iostream>
#include<list>

#define X 2000000

using namespace std;

list<long long> lst={2ll,3ll};

bool divideByAnyPrime(long long a)// checks if the number a is divisible by any prime in the list (lst)
{

    for( auto x:lst )
        if( a%x == 0 )
            return true;
    return false;
}

long long getNextPrime()//adds next prime number to list
{

    long long a=lst.back()+2;
    for( ; divideByAnyPrime(a); a+=2);
    lst.push_back(a);

    return a;

}


int main()
{
    long long sum=5ll;//sum of already existing elements 2 and 3
    while(lst.back()<=X)
    {
        sum+=getNextPrime();
    }
    sum-=lst.back();
    lst.pop_back();//as our list will contain one element at the last which we don't want

    cout<<"\nSum is "<<sum;

}

Answer 1

The algorithm itself is nowhere as efficient as it could be, but let's focus on your implementation instead:

---

Choosing appropriate data types

list<long long> lst={2ll,3ll};

Why bother with a list, and why bother with with long long?

Only use a list if you need random inserts with a cached iterator. In your case, an vector would have fit much better.

The datatype long long is also several magnitudes larger than what would have been needed. The specified maximum of 2 million even fits safely within a 32bit signed integer. Even though this probably doesn't matter much, since when you compile your code on an Unixoid 64bit system, even the basic (non-long) int is usually 64bit.

---

for( auto x:lst )
    if( a%x == 0 )
        return true;
return false;

Checking the complete list is complete overkill. The biggest prime factor you need to check is \$\sqrt{n}\$. To see why, take a prime factor \$p>\sqrt{n}\$. Since \$p\$ divides \$n\$, there exists another integer \$q=n/p\$, and \$q<\sqrt{n}\$. Either \$q\$ is prime, or it is composite and has a smaller prime factor. Either way, \$n\$ has a prime factor smaller than \$\sqrt{n}\$, so checking larger factors is necessary. Note that you do need to include \$\sqrt{n}\$ since it could be the case that \$n\$ is the square of a prime (e.g. \$9\$ or \$25\$).

---

bool divideByAnyPrime(long long a);

While it is possible and correct to search for prime numbers this way, it's not very efficient. Divisions are a lot more expensive than multiplications, or even additions. Even if this is "only" an integer, and not a floating point type.

If you want to find large quantities of primes, either use a sieve to process large blocks of potential prime candidates at once, or at least use one of the many prime number heuristics to eliminate number from which you know that they are certainly non-prime.

Answer 2

Here are a number of things that may help you improve your program.

Use a better algorithm

As already mentioned in the comments, a Sieve of Eratosthenes is going to be much, much faster than the current method. Generally speaking, doing division is a computationally expensive operation. For example, a simple Sieve program to solve this same problem takes 0.7 seconds on my machine, while your existing program takes almost 5 minutes (4:58.4). However, we can still make considerable improvements without changing the basic algorithm you've already implemented. The rest of the review concentrates on helping you improve your existing code and algorithm.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Consider improving names

I think divideByAnyPrime is not a terrible function name (although I'd probably call it isComposite), but X and lst are very poor variable names. A good name should suggest something about what it contains. For example, I've renamed X to MAXNUM in the next suggestion.

Prefer constexpr to old-style #define

Rather than using a #define for X the code could use a constexpr:

constexpr long long MAXNUM{2000000};

The advantage is that the value has an associated type.

Eliminate global variables where practical

The code declares a global variable to contain the list of primes. Global variables obfuscate the actual dependencies within code and make maintainance and understanding of the code that much more difficult. It also makes the code harder to reuse. For all of these reasons, it's generally far preferable to eliminate global variables. For MAXNUM, simply put it at the top of main. For the list of primes, use the next suggestion.

Encapsulate functions and data within a class

Since you're writing in C++, I'd suggest making a class. Here's the class declaration:

class Primes final : public std::list <long long>
{
public:
    Primes()
        : std::list<long long>{2,3}
    {
        for (auto n = back()+2; n <= MAXNUM; n+=2) {
            if (isPrime(n)) {
                push_back(n);
            }
        }
    }
private:
    static constexpr long long MAXNUM{2000000};
    bool isPrime(long long a) const;
};

Notice that MAXNUM is now a member of the Primes class and that the function isPrime is used instead of divideByAnyPrime. Its sense is also inverted such that it only returns true if the passed number is prime.

Think carefully about the mathematics

Within the routine that check for divisibility by any existing prime, there's no need to go all the way to the end of the array. If a number \$N\$is composite, its smallest factor must be \$\le \sqrt{N}\$. This suggests that one way to write an isPrime function would be this:

bool Primes::isPrime(long long a) const
{
    long long sqrta = std::sqrt(a);
    for (auto it = ++begin(); *it <= sqrta; ++it) 
        if( a % (*it) == 0 )
            return false;
    return true;
}

Note that this also skips the first item in the list, which we know is 2.

Use standard functions

Calculating the sum is actually easily done using a standard generic algorithm:

int main()
{
    Primes primes;
    long long sum = std::accumulate(primes.begin(), primes.end(), 0ll);
    std::cout << "Sum is " << sum << "\n";
}

Results

With all of these changes, the time drops to 1.14 seconds on my machine, which is a considerable improvement over the original 5 minutes.