Project Euler problem 78:Let \$p(n)\$ represent the number of different ways in which \$n\$ coins can be separated into piles. For example, five coins can be separated into piles in exactly seven different ways, so \$p(5)=7\$.Find the least value of \$n\$ for which \$p(n)\$ is divisible by one million.I used Euler's recurrence relation for the partition of \$n\$, together with the fact that modular addition is distributive: $$(a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n.$$#include <iostream>#include <vector>using namespace std;int main(){  // generalized pentagonal numbers  vector<int> g = vector<int>({1, 2}); // g_1 = 1, g_-1 = 2   // integer partitions  vector<int> p = vector<int>({1}); // p_0 = 1  for (int n = 1; n ; n++) {    if (g.back() <= n) {      int k = g.size()/2 + 1;      g.push_back(k*(3*k - 1)/2);      k *= -1;      g.push_back(k*(3*k - 1)/2);    }    int p_n = 0;    for (vector<int>::iterator g_k = g.begin(); *g_k <= n; ++g_k) {      if ((g_k - g.begin())/2 % 2 == 0) {        p_n += p[n - *g_k];      } else {        p_n -= p[n - *g_k];      }    }    p.push_back(p_n % 1000000);     if (p.back() < 0) p.back() += 1000000;    if (p.back() == 0) {      cout << n << endl;      break;    }  }  return 0;}My i7 handles this in ~25ms, but my circa 2008 32-bit centrino needs 600ms. Is there any way that I can squeeze more performance out of the above code? Also, with the exception of removing using namespace std;, is there anything I can do to make the code cleaner/more readable/more presentable?
Project Euler 78: Counting Partitions
c++;performance;programming challenge;combinatorics
I see a few minor things that may help you improve your code.Use list initializers directlyThe declarations of g and p are more complex than they need to be.  Instead, one can use list initializers directly:vector < int >g{1, 2};vector < int >p{1};This makes the code more readable.Use auto where it helps readabilitySimilarly, the inner for loop can be made a bit simpler using auto:for (auto g_k = g.begin(); *g_k <= n; ++g_k) {Use const where practicalIn this case, const isn't used explicitly, but a const iterator may be used in that same inner loop:for (auto g_k = g.cbegin(); *g_k <= n; ++g_k) {Avoid costly mathematical operatorsBoth the / and % operators tend to be somewhat more computationally costly than + and -.  For that reason, if performance is your goal, you might want to seek ways to minimize the use of those more costly operators.  For instance, instead of this line:if ((g_k - g.begin()) / 2 % 2 == 0) {You could write this instead (assuming 2's complement representation):if ((g_k - g.cbegin()) & 2) {On my machine, this gives a measurable speed increase.Simplify in-loop operations as much as possibleThe first if statement uses multiplication and division to calculate the values, but a simple analysis of the numbers shows that it's a fairly simple series, and so the numbers can be calculated using only addition:int k = 2;int m = 5;int dm = k+m;for (int n = 1; n; n++) {    if (g.back() <= n) {        g.push_back(m);        g.push_back(m + k++);        m += dm;        dm += 3;    }    // etc.Use longer, more meaningful namesNames like p and g are not very descriptive. Because this is a fairly short program and mathematical in nature, this isn't a terrible flaw, but it's worth considering if there might be more meaningful names that could be used. Eliminate magic numbersThis code has a number of inscrutable magic numbers, that is, unnamed constants such as 2, 3, 1000000, etc.  Generally it's better to avoid that and give such constants meaningful names.  That way, if anything ever needs to be changed, you won't have to go hunting through the code for all instances of 2 and then trying to determine if this particular 2 is relevant to the desired change or if it is some other constant that happens to have the same value.Don't abuse using namespace stdPutting using namespace std at the top of every program is a bad habit that you'd do well to avoid.  Know when to use it and when not to (as when writing include headers).  In this particular case, I happen to think it's perfectly appropriate because it's a single short program that and not a header. Some people seem to think it should never be used under any circumstance, but my view is that it can be used as long as it is done responsibly and with full knowledge of the consequences.  