[java] 약수의 개수 구하는 알고리즘

알고리즘 문제 풀이 중 약수의 개수를 구하는 예제가 있었음.

 

예를 들어) 약수의 개수가 짝수인지 홀수인지 판별하여 값을 더하거나 빼시오.

 

제가 생각한 약수의 개수가 짝/홀수인지 판별하는 방법은

 

1. 숫자를 제곱근으로 나눈다.

2. 제곱근이 실수가 아닌 정수로 딱 맞아 떨어지는지 판별한다.

 

여기서 제곱근이 정수로 딱 맞아 떨어지면 다시 제곱을 하면 원래의 수가 나타나기 때문에 약수의 개수가 홀수,

아니라면 짝수가 나타난다고 판별했음.

 

예시1) 14 : 1, 2, 7, 14 → 약수 : 4개, 제곱근 : 3.xxx

예시2) 16 : 1, 2, 4, 8, 16 → 약수 : 5개, 제곱근 : 4

 

◎ 코드 구현

 for(int i=시작 숫자; i<=종료 숫자; i++){
    int rootNum = (int)Math.sqrt(i);
    if(Math.pow(rootNum,2) == i){
        // 약수 갯수 : 홀수
        continue;
    }

    // 약수 갯수 : 짝수
}

※ 메소드 설명
1. Math.sqrt() : double 형태, 제곱근을 나타냄
2. Math.pow(대상 숫자, 곱할 횟수) : double 형태, 거듭제곱을 나타냄

 

 

위와 같이 코드를 구성해 제곱근을 정수로 만들고,

다시 제곱했을 때, 원래 숫자와 동일하면 약수의 개수가 홀수 개라고 판단했습니다.

 

제곱근을 사용한 이유

→ 제곱근을 기준으로 약수의 개수가 양쪽으로 대칭