[Java] 약수 구하기

1. 개요

약수 구하는 방법은 기본적으로 그 수와 나눠서 나머지가 없다면 그것은 약수가 됩니다.

하지만 우리는 더 새로운 방법을 찾아봅시다.

2. 본문

만약 우리가 약수를 구한다고 할 때 단순히 생각나는 것은 약수를 전부다 구하는 것 입니다.

하지만 21억의 약수를 구한다고 하면 21억번을 반복해야할까요?

        int num = Integer.parseInt(st.nextToken());
        int pos = Integer.parseInt(st.nextToken());

        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 1; i<=num; i++){
            if(num % i == 0) list.add(i);
        }
        if(list.size() < pos) System.out.println(0);
        else System.out.println(list.get(pos-1));

정말 간단하게 생각하면 이렇게 풀면 될 것 입니다.

하지만 더 효율적인 방법으로 해볼까요?

        int num = Integer.parseInt(st.nextToken());
        int pos = Integer.parseInt(st.nextToken());

        ArrayList<Integer> list = new ArrayList<>();
        // 제곱근 생성
        int repeat = (int) Math.sqrt(num);
        for (int i = 1; i <= repeat; i++) {
            if (num % i == 0) {
                list.add(i);
                if (num / i != i) list.add(num / i);
            }
        }
        Collections.sort(list);
        if (list.size() < pos) System.out.println(0);
        else System.out.println(list.get(pos-1));

바로 제곱근을 통해 약수를 구하는 방법입니다. 이렇게 되면 반복횟수의 제곱근 만큼만 반복하죠.

1. 1 ~ 제곱근 만큼 반복하기

2. 만약 num을 i로 나눈 나머지가 0이라면 -> 약수

3. 추가로 num을 i로 나누면? -> i에 대응하는 수 -> 약수 (하지만 중복처리를 위해 num / i != i)

 

간단하게 12를 예로 들어보겠습니다.

12 = 1 2 3 4 6 12, 제곱근은 3.xxxx

1과 대응하는 숫자는 12, 2와 대응하는 숫자는 6, 3과 대응하는 숫자는 4가 됩니다.

 

반면에 25를 예로 들어볼까요?

25 = 1 5 25, 제곱근은 5

1과 대응하는 숫자는 25, 5와 대응하는 숫자는 5입니다. 25 / 5 = 5 이기 때문에 중복처리를 해줘야 하죠.

3. 문제

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

2501번: 약수 구하기

해당 문제에서는 제곱근으로 구해도 되고 전체 숫자를 반복해도 풀립니다.

하지만 반복횟수가 더 작은 제곱근으로 푸는 것이 더 좋겠죠?