프로그래머스 - 약수의 개수와 덧셈 java :: 월간 코드 챌린지 시즌2 :: 77884

문제 링크

코딩테스트 연습 - 약수의 개수와 덧셈 | 프로그래머스 (programmers.co.kr)

---

문제 풀이

1번 풀이

public int solution(int left, int right) {
    int answer = 0;
    for( int cur=left; cur<=right; cur++ ) {
        int num = cur;
        int total = 1 , count = 0;
        for ( int i = 2; i <= Math.sqrt(num); i++ ) {
            while ( num % i == 0 ) {
                count++;
                num /= i;
            }
            if(count != 0) { 
                total *= (count+1);
                count = 0;
            }
        }
        if( num != 1 ) {
            total *= 2;
        }

        answer = total % 2 == 0 ? answer + cur : answer - cur;
    }

    return answer;
}

소인수 분해를 활용한 방법입니다.

예를 들어 24의 약수는 { 1, 2, 3, 4, 6, 8, 12, 24 } 입니다.

24의 소인수를 구하면 $2^{3}, 3^{1}$ 입니다.

각 소인수의 제곱수+1 을 모두 곱하면 약수의 개수가 됩니다.

즉, $(3+1) * (1+1) = 8$

그러므로 24의 약수의 개수는 8입니다.

반복문을 제곱수까지만 순회하는 이유는 아래 성질 때문입니다.

어떤 수 n이 두 개 이상의 곱셈(인수)으로 나타낼 수 있을 때 인수 중 한 개 이상은 반드시 $\sqrt{n}$ 보다 작거나 같은 수입니다.

그러므로 소인수를 구할 때에는 제곱수보다 높은 수는 탐색할 필요가 없습니다.

만약 계속 순해하며 소인수를 구했는데도 num이 0이 되지 않았다면 그 수가 바로 소인수입니다.

14를 예를 들어보겠습니다.

$\sqrt{14} = 3.741...$ 인데

그렇다면 2 ~ 3 까지 순회하며 소인수를 찾습니다.

n	i	n % i
14	2	0
7	2	1
7	3	1

반복문 종료 시 n은 소인수로 계속 나누기 때문에 반복문에서 소인수를 모두 구했다면 반드시 1이 되어야 합니다.

2 라는 소인수를 구했고 반복문이 끝났지만 n은 아직 7입니다.

그러므로 7도 소인수입니다.

테스트 처리속도

• 🔥 평균 0.15ms

2번 풀이

소인수분해 공식으로 이쁘게 풀었는데 다른 사람의 풀이 중 더 완벽한 코드가 있었습니다.

public int solution(int left, int right) {
    int answer = 0;
    for ( int num=left; num<=right; num++) {
        if(num % Math.sqrt(num) == 0) answer -= num;
        else answer += num;
    }

    return answer;
}

바로 제곱수의 성질을 이용한 방법입니다.

어떤 수 n이 제곱수이면 약수의 개수는 반드시 홀수입니다.

그 이유는 제곱수 16으로 예를 들면

$\sqrt{16} = 4$

모든 약수는 짝꿍이 있는데 제곱수는 짝꿍이 없는 약수하나 하나 있으므로 홀수가 되는 것입니다.

16 의 약수 = { 1, 2, 4, 8, 16 }

$1 * 16 = 16$ 1과 16이 짝꿍

$2 * 8 = 16$ 2와 8일 짝꿍

$4 * 4 = 16$ 4는 혼자

이렇게 다 짝궁이 있어야 되는데 4는 짝꿍이 없으니까 제곱수로 나누어 떨어지는 수의 약수의 개수는 반드시 홀수입니다.

테스트 처리속도

• 🔥 0.05ms