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

#include <iostream>
#include <cmath>

using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll n; cin >> n;
    ll ans = n;

    for (ll i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            ans -= ans / i;

            while (n % i == 0) {
                n /= i;
            }
        }
    }

    if (n > 1)
        ans -= ans / n;

    cout << ans;

    return 0;
}

 

오일러 피 함수를 구현하는 문제

GCD(n, k) = 1은 1 ~ n의 범위에서 n과 서로소인 자연수 k를 뜻한다

예를 들어 n = 10이면 1 2 3 4 5 6 7 8 9 10, 4개가 존재한다

n = n - n / k 연산(코드내에서는 k 대신 i 사용)을 반복하면 된다

 

 

for문 i의 범위를 n의 제곱근으로 설정하지 않아 시간 초과가 났던 문제