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

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
#include

#define X 2000000

using namespace std;

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

}

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 
{
public:
    Primes()
        : std::list{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.

StackExchange Code Review Q#144423, answer score: 21