Phi function

Урок 12 из 20 курса Математические головоломки на Coddy.

Функция Эйлера, φ(n) [иногда называемая функцией фи], используется для определения количества чисел, меньших n, которые являются взаимно простыми с n. Например, так как 1, 2, 4, 5, 7 и 8 меньше девяти и взаимно просты с девятью (что означает, что наибольший общий делитель всех этих чисел и 9 равен 1),

то результатом функции фи будет φ(9)=6. Поскольку мы научились вычислять GCD, мы можем вычислить (с помощью функции GCD) функцию фи.

Задание

Сложно

Напишите функцию phi, которая принимает число n и возвращает φ(n).

Попробуйте сами

#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;
}