오일러 피

수학에서 오일러 피 함수 P[N] 의 정의는 1부터 N가지 범위에서 N과 서로소(공약수가 1뿐인 관계)인 자연수의 개수를 뜻한다.

 

오일러 피 함수 구현

public class EulerPhiFunction {
    public static void main(String[] args) {
        int n = 10; // 원하는 정수 n 값 입력

        int result = eulerPhi(n);
        System.out.println("Euler's Phi function for " + n + " is: " + result);
    }

    // 오일러 피 함수 구현
    public static int eulerPhi(int n) {
        int result = n;

        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                while (n % i == 0) {
                    n /= i;
                }
                result -= result / i;
            }
        }

        if (n > 1) {
            result -= result / n;
        }

        return result;
    }
}