# 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 <cmath>
#include <cstdio>
#include <tchar.h>

#include <iostream>
#include <stdexcept>


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 < 0)
throw std::invalid_argument(__nameof(number));
if (number == 0)
return 0;
if (number == 1)
return 1; // 1 is the only number relatively prime to itself

int result = 1; // We're always relatively prime to 1
for (int i = 2; i < number; i++)
{
if (relatively_prime(i, number))
result++;
}

return result;
}

bool prime(int number)
{
if (number < 0)
throw std::invalid_argument(__nameof(number));

int bound = static_cast<int>(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 for undefined behavior/gotchas I didn't see? I'm a beginner so any feedback/critique would be appreciated.

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.

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

• Naming a composite counting function not_pi comes from the convention of writing the prime counting function as pi. – Alexander Gruber Nov 21 '15 at 2:00

A few comments. I am addressing only the C++ aspects not the algorithmic or mathematic aspects.

First, when creating a project with Visual C++,t this is what I do. On the New Project, I choose the Win32 Console Application and then click OK. On the next dialog that appears, I go to Application Settings and uncheck Precompiled headers and SDL checks. I then check Empty Project. So it looks like this. This gives me an empty project. Then I right click on the Source Files folder in the Solution Explore then Add -> New Item to add the source file. This gives you a clean project without the Visual C++ specific precompiled header stuff.

This will allow you to get rid of stdafx.h as you don't need it. You can directly include iostream, and stdexcept at the beginning of your golf.cpp file.

Second, names with double underscores are reserved. In addition, the nameof the parameter is not helpful as there is only 1 parameter. The function name is IMHO more useful, and you can use __func__ there.

Third, I would just move golf::main into the global namespace and get rid of the glue main.

Here is how my code ended up looking

        #include <iostream>
#include <stdexcept>
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 < 0)
throw std::invalid_argument(__func__);
if (number == 0)
return 0;
if (number == 1)
return 1; // 1 is the only number relatively prime to itself

int result = 1; // We're always relatively prime to 1
for (int i = 2; i < number; i++)
{
if (relatively_prime(i, number))
result++;
}

return result;
}

bool prime(int number)
{
if (number < 0)
throw std::invalid_argument(__func__);

int bound = static_cast<int>(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(__func__);
if (number <= 3)
return 0;

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

return result;
}

}
int main()
{
using namespace golf;

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

return 0;
}