Beakjoon] GCD(n, k) = 1 aka.오일러의 피 (백준 11689 코테) - 정수론 (C++)

---

🅰️문제주소 : https://www.acmicpc.net/problem/11689

 

🚩문제 

 

 

🪡풀이 

 - 주어진 수에서 그 수보다 작은 자연수 중 최대공약수가 1이 되는 수(서로소)의 개수를 구하는 것으로 오일러의 피 함수를 구현할 줄 아는지 묻는 문제
 - 소수를 구하는 에라토스테네스의 체와 비슷하게 구현가능한데 배수를 0으로 지우는 부분 대신 P[i] = P[i] -[Pi]/K 로 변경해 주면 된다
 - 해당문제는 한번의 입력만 주어지기에 따로 배열에 저장할 필요 없이 매번 새로 구하게 하면 된다

 

 

☕코드는 아래 숨김

#include <iostream>
#include <vector>
#include <math.h>

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

    long long n;

    std::cin >> n;

    long long result = n;

    for (int i = 2; i <= std::sqrt(n); ++i) { //제곱근까지만 진행함
        if (n % i == 0) { //i가 소인수인지 확인함 
            result = result - result / i; //결과값 개수를 업데이트 함
            while (n % i == 0) { //소인수 i를 바로바로 지움 중복삭제를 방지
                n /= i;
            }
        }
    }
    if (n > 1) { //제곱근까지 진행했기에 1개의 소인수가 누락될 수 있음 
        result = result - result / n;
    }


    std::cout << result;
    return 0;
}

 

💡알게 된 것 

 - 오일러의 피 함수
 - 기초 수학 용어들 remind...
     1) GCD : 최대공약수
     2) 서로소 : 두 수의 최대공약수가 1, 최소공배수는 두수의 곱  
     3) 소인수 : 자연수를 나누어 떨어지는 수 중 소수인 것 (10의 경우 1 2 5 10 중 2, 5에 해당)

---