[BaekJoon] 23832 서로소 그래프 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int nodeNum;

    static void input() {
        Reader scanner = new Reader();

        nodeNum = scanner.nextInt();
    }

    /*
        1부터 N까지 N개의 숫자에 대해 각 숫자의 서로소의 개수를 찾는 문제
        그러나, 간선은 양방향 간선이므로 2와 3은 서로소지만 2에서 3을 세고, 3에서 2를 세면 중복이 된다!
            -> 그러므로 가장 큰 수부터 시작하여 1보다 큰 수까지 1씩 아래로 내려오면서 서로소의 개수를 구하고 이를 누적한다
            -> 그렇다면 중복의 문제가 사라진다

        서로소의 개수를 단순한 for문을 통해 찾게 되면 O(N^2)이 되므로 시간 초과이다!
        오일러 피 함수를 사용하면 숫자 n에 대한 서로소의 개수를 찾을 수 있으니 이를 이용한다!
     */
    static void solution() {
        int answer = 0;

        for(int num = nodeNum; num > 1; num--) {
            answer += eulerPhi(num);
        }

        System.out.println(answer);
    }

    static int eulerPhi(int num) {
        int result = num;

        for(int divisor = 2; divisor * divisor <= num; divisor++) {
            if(num % divisor == 0) {
                while(num % divisor == 0) {
                    num /= divisor;
                }

                result -= result / divisor;
            }
        }

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

        return result;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}