Code Golf Challenge: Calculate Phi (not Pi)

I'm a newbie to C++ (coming from C#) and I decided to complete this Code Golf challenge for fun (though I definitely wouldn't say it's short). Essentially, the challenge was to calculate the phi(not_pi()) of all the numbers from 1 to 100, and print them out in a loop, where

• phi(n) is the number of integers less than or equal to n that are relatively prime to n.

• not_pi(n) is the number of composites less than or equal to n.

Here is my code (I'm using Visual C++ 2015):

stdafx.h

#pragma once

#include "targetver.h"

#include 
#include 
#include 

#include 
#include 

golf.cpp

#include "stdafx.h"

#define __nameof(var) #var

namespace golf
{
    int gcd(int left, int right) noexcept
    {
        if (right == 0)
            return left;
        return gcd(right, left % right);
    }

    bool relatively_prime(int left, int right) noexcept
    {
        return gcd(left, right) == 1;
    }

    int phi(int number)
    {
        if (number (std::floor(std::sqrt(number)));
        for (int i = 2; i <= bound; i++)
        {
            if (number % i == 0)
                return false;
        }

        return true;
    }

    int not_pi(int number)
    {
        if (number < 0)
            throw std::invalid_argument(__nameof(number));
        if (number <= 3)
            return 0;

        int result = 1;
        for (int i = 6; i <= number; i++)
        {
            if (!prime(i))
                result++;
        }

        return result;
    }

    int main()
    {
        for (int i = 1; i <= 100; i++)
        {
            std::cout << i << " " << phi(not_pi(i)) << std::endl;
        }

        return 0;
    }
}

int main()
{
    // Glue code because I didn't realize main() 
    // was supposed to be in the global namespace.
    return golf::main();
}

Any tips on how I could improve my C++ code? Specifically, is there anything I could do to make it more "modern"/C++11-like, or practices I should follow? Are there any sources fo

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).

StackExchange Code Review Q#111152, answer score: 4