12
\$\begingroup\$

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;

}
\$\endgroup\$
  • 10
    \$\begingroup\$ Google "sieve prime". That should give you all the necessary information \$\endgroup\$ – miscco Oct 17 '16 at 10:52
  • 7
    \$\begingroup\$ My old buddy Erastothenes can probably help you out with this problem \$\endgroup\$ – Brian Sutherland Oct 17 '16 at 17:10
  • \$\begingroup\$ Possible duplicate of Prime Number calculation bottleneck \$\endgroup\$ – Casey Oct 18 '16 at 6:13
  • \$\begingroup\$ @Casey Our threshold for duplication is very high. Unless the two questions have the same code, they aren't duplicates. This is so even if many of the answers will be essentially the same. That's not to say that it is unreasonable to link to previous questions. Just not to close new questions as duplicates of previous questions unless they are essentially exact duplicates. \$\endgroup\$ – mdfst13 Oct 18 '16 at 10:54
19
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ "even the basic (non-long) int is usually 64bit" - Linux (gcc) on amd64 usually has a 32-bit int and a 64-bit long \$\endgroup\$ – ilkkachu Oct 17 '16 at 12:42
  • \$\begingroup\$ After changing all long long to int and list to vector now my program runs in 0.57 second. I'm wondering is it mattered so much !!😮 \$\endgroup\$ – Gaurish Gangwar Oct 17 '16 at 12:56
  • 2
    \$\begingroup\$ @GaurishGangwar Data locality, and vector instructions. A vector is actually backed by a plain, compact field. Accessing neighboring elements is blazing fast, respectively the CPU can even access a whole range of elements at once by using vector instructions. A list on the other hand stores each single element in an individual element which is linked to the next element by an additional pointer. That's an incredible amount of additional work just to traverse a list. \$\endgroup\$ – Ext3h Oct 17 '16 at 13:06
  • \$\begingroup\$ Ohh, thank you again for your valuable advice. \$\endgroup\$ – Gaurish Gangwar Oct 17 '16 at 13:35
  • \$\begingroup\$ you can even look for 'no. of primes' below 2 million on the internet and call reserve() over that vector with that size. Since all you're trying is to calculate it's sum, this isn't cheating but optimization process ;) \$\endgroup\$ – Abhinav Gauniyal Oct 18 '16 at 7:05
21
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you @Edwards Now I can see that I've used C++ in C style. You've used it in proper object oriented way. 👍 \$\endgroup\$ – Gaurish Gangwar Oct 17 '16 at 13:50
  • \$\begingroup\$ On my machine, it is faster as I've written it. Any proposed optimization should be tested to make sure it really does create an improvement; the changes I showed were all actually tested and measured as shown in the answer. \$\endgroup\$ – Edward Oct 17 '16 at 14:07
  • 2
    \$\begingroup\$ If this answer only had your bold titles it would still be a great answer. Wish you did code reviews at my job back when I was a programmer. \$\endgroup\$ – corsiKa Oct 17 '16 at 18:17
  • \$\begingroup\$ I would like to note that it will be dangerous to use list<>* to call the destructor of Primes. \$\endgroup\$ – Incomputable Oct 18 '16 at 7:50
  • \$\begingroup\$ @Olzhas: One could either make the class final or write a virtual destructor if that were a concern. My advice: "don't do that." \$\endgroup\$ – Edward Oct 18 '16 at 11:24

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.