자바 - 정수의 약수 개수 구하기

정수의 약수 개수 구하기

이번에는 일반 수학의 관련한 문제를 GPT를 통해 만들고 해결해보았다.
우선 일반 수학과 관련하여 GPT가 만들어준 문제는 정수의 약수 개수 구하기이다.
처음에는 문제가 너무 쉬워서 단순 반복문을 이용하여 접근하는 것을 생각하였다.
입력된 정수 만큼 반복문을 돌리고 정수의 i 값을 몫 연산하여 나머지가 0일 경우 CNT를 증가하는 것이였다.
하지만 이것이 비효율적인 코드라는 것을 뒤늦게 알게되어 다음과 같이 수정하였다.

문제 : 정수의 약수 개수 구하기

정수 (N)이 주어졌을 때, (n)의 약수의 개수를 구하는 프로그램을 작성하라.
입력 예시.

N : 12 

RESULT : 6

 

N : 28

RESULT : 6

 

정답 코드 및 해설

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

public class main {
    public static void main(String[] args) throws IOException {
      
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int cnt = 0;
        for (int i = 1; i <= Math.sqrt(n); i++) {
            if(n%i ==0){
                cnt++;

                if (i != n/i) {
                    cnt++;
                }
            }
        }
        System.out.println(cnt);
    }
}

위와 같이 계산을 하면 처음에 생각했던 방법의 2/1 만큼의 시간 복잡도를 줄일 수 있게 된다.

그렇다면 문제의 접근 방식이 어떻게 해결되는지 확인해본다.

 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 int n = Integer.parseInt(br.readLine());

위는 BufferReader 클래스를 이용하여 값을 입력받는 코드이다.

위 내용은 다음에 정리를 자세하게 진행하겠습니다.

        int cnt = 0;
        for (int i = 1; i <= Math.sqrt(n); i++) {
            if(n%i ==0){
                cnt++;

                if (i != n/i) {
                    cnt++;
                }
            }
        }
        System.out.println(cnt);

cnt는 입력된 값의 약수의 개수를 카운트 하기 위한 변수이다.

여기서 다른 부분은for 부분으로 처음에 생각 했던 for의 조건은 for(i=1; i <= n; i++)와 같은 형식이다. 
그러나 for 현재 for는 Math.sqrt(n)으로 되어있다. Math.sqrt()는 입력된 값의 제곱근을 구하여 double 타입으로 반환하는  함수이다.예를 들면 n = 25일 경우 Math.sqrt(n)의 결과는 5.0이 된다. 

이렇게 작성하게 되면 반복 회수가 엄청나게 줄어들게 되지만 약수를 찾는데 부족한 반복 횟수를 갖게 된다. 

하지만 이 문제는 다음과 같이 해결할 수 있게 된다. 25의 약수는 1, 5, 25 총 3개이다.

즉 n%i == 0과 같은 값은 일단 약수이며 이 약수를 반대로 계산해도 동일한 약수가 도출된다.

ex ) n(25) /i(i) = = 0,n(25)/i(25) == 0 이와 같이 끝나기 i != n/i을 하게 되면 한번에 2개의 약수를 구할 수 있게 된다. 

다른 약수인 5를 예로 보면 n(25) % 5 ==0, 약수의 조건에 해당되며 n/i = 5가 되어 결국 5가 되어 이는 중복 약수가 되기 때문에 제거를 하게 된다.