https://www.acmicpc.net/problem/11689

주어진 n에 대해 ϕ(n)을 계산하면 됩니다.(ϕ : euler pi function)

n의 소인수를 $p_1, p_2, p_3, .., p_k$라고 할 때, $ϕ(n) = n \times (1-1/p_1) \times (1-1/p_2) \times .. \times (1-1/p_k)$라는 성질이 있고 이 성질에 충실하게 구현을 하면 됩니다.

https://github.com/encrypted-def/BOJ/blob/master/11689.cpp