[백준] [C++] 11689번 GCD(n, k) = 1 (오일러 피 함수)

1. 문제

 

11689번: GCD(n, k) = 1 (acmicpc.net)

11689번: GCD(n, k) = 1

 

2. 풀이 

오일러 피 함수는 n과 서로소인 1부터 n까지의 정수를 리턴하는 함수이다.

오일러 피 함수 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

오일러 피 함수 - 위키백과, 우리 모두의 백과사전

 

#include <bits/stdc++.h>
 
using namespace std;
long long n;
 
long long factorSimple()
{
    long long ret = n;
    long long sqrtn = sqrt(n);
    for (long long div = 2; div <= sqrtn; div++) {
        if(n%div == 0) {
            ret = ret / div * (div - 1);
        }
        while(n%div==0) {
            n /= div;
        }
        
    }
    if(n != 1) { 
        ret = ret / n * (n-1);
    }
    return ret;
}
 
int main() {
    cin>>n;
    long long  answer = factorSimple();
    cout<<answer;
}