백준 4355 서로소

https://www.acmicpc.net/problem/4355

void countCoPrime(int n) {
        int[] arr = new int[n+1];

        for (int i = 1; i < arr.length; i++) {
            arr[i] = i;
        }

        for (int i = 2; i <= n; i++) { // 자꾸 2부터 시작해야한다는 걸 까먹는다..! 2부터 시작
            if(arr[i] == i){
                for (int j = i; j <= n; j += i) {
                    arr[j] = arr[j] - (arr[j] / i);
                }
            }
        }
        System.out.println(arr[n]);
    }

Euler phi

    int eulerPhi(int n) {
        int[] arr = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            arr[i] = i;
        }

        for (int i = 2; i < n + 1; i++) {
            if (arr[i] == i) {
                for (int j = i; j < n + 1; j += i) {
                    arr[j] = arr[j] - (arr[j] / i);
                }
            }
        }

        for (int i = 1; i < n + 1; i++) {
            System.out.println(arr[i]);
        }
        System.out.println("------------------");

        return arr[n];
    }