On the other side of things, I show by construction how many well-known functions can be implemented as primitive recursive functions: https://www.nayuki.io/pag

On the other side of things, I show by construction how many well-known functions can be implemented as primitive recursive functions: https://www.nayuki.io/page/primitive-recursive-functions https://www.nayuki.io/page/primitive-recursive-functions One challenge I found is that I have to set the upper bounds conservatively. For example for sqrt(n), the loop actually counts all the way up to n, because in the worst case, sqrt(1) = 1. As another example, to find the nth prime number, I search up to 2^n, because a conservative lower bound is that there is at least one prime number between 2 and 4, between 4 and 8, between 8 and 16, etc.