I wrote the following solution to the coin partition problem. I use Euler's recurrence relation for the partition of n and that modular addition is associative; (a + b) % n = (a % n) + (b % n) % 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 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?