Putting using namespace std at the top of every program is a bad habit 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.
Putting 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.
Putting 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.
I see a few minor things that may help you improve your code.
Use list initializers directly
The 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 readability
Similarly, 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 practical
In 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 operators
Both 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 possible
The 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 names
Names 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 numbers"
This 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 std
Putting 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.