[Java] 38. N값 이하의 서로소 개수 구하기

package algo;

import java.util.Scanner;

public class Coprime01 {
    public static void main(String[] args) {

        // 서로소란 ? a와 b의 최대 공약수가 1인 것을 서로소라고 한다.
        //1. N값 이하의 서로소 개수 구하기
        Scanner sc = new Scanner(System.in); // 스캐너를 통해 사용자로부터 입력 받는다.
        System.out.println("정수를 입력해주세요 : ");
        int N = sc.nextInt(); // 입력받은 숫자를 N에 저장한다.
        int count = 0; // 개수를 세어보기 위한 count 변수를 만든다. 0으로 초기화
        int[] arr = new int[N];

        for (int i = 1; i < N; i++) {
            if (Util.gcd(N, i) == 1) {
                count++;
            }
        }
        System.out.println(count);
    }
}