[자바 알고리즘] 57. 서로소 (오일러 피함수)

package Test01;

import java.util.Scanner;

public class Euler {

    // 오일러의 피 함수 계산
    public static int euler(int n) {
        int result = n;

        // 2부터 n까지 모든 소수에 대해
        for (int i = 2; i * i <= n; i++) {
            // i가 n의 약수라면
            if (n % i == 0) {
                // n을 i로 나누어가며, n에서 i의 배수 제거
                while (n % i == 0) {
                    n /= i;
                }
                // 오일러 피 함수 공식에 따라 계산
                result -= result / i;
            }
        }

        // 마지막 남은 소수에 대해 처리
        if (n > 1) {
            result -= result / n;
        }

        return result;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("자연수 n을 입력하세요: ");
        int n = scanner.nextInt();

        // 오일러의 피 함수 계산하여 출력
        System.out.println("n 이하의 자연수 중 n과 서로소인 자연수의 개수: " + euler(n));
    }
}