Code Golf Challenge: Calculate Phi (not Pi)
I would move your main outside of the golf namespace instead of glueing code together.
The not_pi name is confusing to me because I would assume its a function that checks if n is not 3.1415926..., which it clearly doesn't do.
Another suggestion is to expose most of this functionality in a golf.h header so that you can call this code from some where else. In that case move main completely outside golf.cpp and into main.cpp or similar.
Other than that you should add documentation/comments to all non-trivial functions.

Now let's talk performance.
GCD
If you have extra memory handy, then you can optimize your gcd calls through a technique known as memoization.
Basically, for small left and right (which I would rename to a and b) you would calculate the result once and then store it for future reference. This requires a minor modification to the gcd function to check if it has a pre-calculated result for that problem, and then return the result in that case. The reason this will help in the long run is that if you trace the calls to gcd you will note that it will usually end up in the smaller values and calculate these results over and over again.
I would use a 2D array or a vector of vectors for this purpose and store up to gcd(1000, 1000) or so (if you have more memory free, feel free to increase this while your code execution time increases on the desired input).
Prime
An easy optimization is checking the i = 2 case separately from the odd numbers which allows you to loop by 2's and so is roughly a 2x speedup.
There are also much faster algorithms for this than brute force division such as Miller-Rabin which can be made deterministic for a finite range of integers (a potentially very large range, much larger than 64 bit integer maximum).