Phi function

Lesson 12 of 20 in Coddy's Mathematical Riddles course.

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine (meaning the greatest common divisor between all these numbers and 9 is the number 1),

then the result of the phi function φ(9)=6. Since we learned to calculate GCD, we can calculate (with the help of GCD function) phi function.

Challenge

Hard

Write a function phi which gets a number n and returns φ(n).

Try it yourself

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "solution.h"

int main() {
    int n;
    if (scanf("%d", &n) != 1) n = 0;
    int r = phi(n);
    printf("%d\n", r);
    return 0;
}