The following code finds all the numbers that are coprime to a given n.
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.
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.