Functional programs don't rely on loops and the associated overhead of tracking the state of loops. Instead, functional programs try to rely on the much simpler approach of recursive functions. In some languages, the programs are written as recursions, but Tail-CallOptimization (TCO) in the compiler changes them to loops. We'll introduce some recursion here and examine it closely in Chapter 6, Recursions and Reductions.
We'll look at a simple iteration to test a number for being prime. A prime number is a natural number, evenly divisible by only 1 and itself. We can create a naïve and poorly-performing algorithm to determine whether a number has any factors between 2 and the number. This algorithm has the advantage of simplicity; it works acceptably for solving Project Euler problems. Read up on Miller-Rabin primality tests for a much better algorithm.
We'll use the term coprime to mean that two numbers have only one as their common factor. The numbers...