totient function

LaTeX4Web 1.4 OUTPUT Euler¢s Totient Function, denoted by f(n), counts the number of integers up to n that are coprime to n and it is denoted by f(n). Coprime means that they do not share any prime factor. For instance, f(10) equals 4 because there are only numbers smaller than 10 and coprime with 10: 1, 3, 7 and 9. In order to compute f(n) it is important to take into account the following properties:
f(ab) = f(a)f(b) if a and b are coprime.
f(pk ) = (p-1)pk-1
Hence, by decomposing n into its prime factors it is relatively easy to compute f(n). The following table shows the computation of f(n) for the first natural numbers.

The following code finds all the numbers that are coprime to a given n.

Coprimes.txt Coprimes.txt
Size : 1.435 Kb
Type : txt

Here you can see an example of the output of the code.

Here we provide the code to compute Euler's totient function using the two properties described above.

PhiEuler.txt PhiEuler.txt
Size : 1.387 Kb
Type : txt

Here you can see an example of the output of the code. 

LaTeX4Web 1.4 OUTPUT Moreover, for the previous codes we need to factorize each number. To do so we use the Sieve of Erathostenes. The Sieve of Eratosthenes is an algorithm that is used in order to find primitive numbers in an effective way. The regular way to find if a number is prime or not is by checking it is divisible by some integer smaller than the square root of this number. However, the Sieve of Eratosthenes finds prime numbers until n in a much faster way. First it erases all the multiples of 2 until n then it erases all the multiples of 3 until n. Then it erases all the multiples of 5 (because 4 is already gone) until n. It keeps repeating this process and so the numbers that remain are prime numbers because they do not have any divisor that could have erased them. The following picture illustrates the process. You can find the code for the Sieve of Erathostenes in the previous two codes.