[백준 4355] 서로소 [C]

백준 - 4355

---

풀이

"백준 11689, GCD(n, k) = 1"를 이용해 풀이했다.

시간초과는 발생하지 않으니 그냥 0을 입력받을 때까지 반복하면된다.

---

소스코드

#include <stdio.h>
int main(){
    long long n;
    while (1){
        scanf("%lld", &n);
        if (!n) break;
        long long euler = n;
        for (long long p = 2; p*p <= n; p++){
            if (n % p == 0) euler = euler/p *(p - 1);
            while (n % p == 0) n = n/p;
        }
        printf("%lld\n", n == 1 ? euler : euler/n *(n - 1));
    }
}

---

출처 및 참고자료

4355번: 서로소

[백준 11689] GCD(n, k) = 1 [C]