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

일반적인 방법

int num=12;

int cnt=0; 
for(int i=1; i<=num; i++){
  if(num % i == 0) cnt++;
}

System.out.println(cnt);

일반적인 방법이다 하지만
방법이 너무 복잡해진다

효율적인 방법

int num=12;

int cnt=0; 
for(int i=1; i*i <= num; i++){
    if(i % i == 0) cnt++;
    else if(number & i == 0) cnt+=2;
}

System.out.println(cnt);

---

• 반복문 시작

for (int i = 1; i * i <= number; i++):
i는 1부터 시작해서 i * i가 number보다 작거나 같은 동안 반복

• i = 1

1 * 1 <= 12는 참
if (i * i == number)는 거짓 (1 != 12).
else if (number % i == 0)는 참 (12 % 1 == 0).
cnt += 2가 실행되어 cnt는 2

• i = 2

2 * 2 <= 12는 참
if (i * i == number)는 거짓 (4 != 12).
else if (number % i == 0)는 참 (12 % 2 == 0).
cnt += 2가 실행되어 cnt는 4

• i = 3

3 * 3 <= 12는 참
if (i * i == number)는 거짓 (9 != 12).
else if (number % i == 0)는 참 (12 % 3 == 0).
cnt += 2가 실행되어 cnt는 6

• i = 4

4 * 4 <= 12는 거짓
반복문 종료

---

이와 같이

12는 2로 나누어짐 = 12는 6으로 나누어짐
이기 때문에 2만 구해도 6은 저절로 구해진다.

절반만 실행해서 약수를 구할 수 있다.

🥑 예제
기사단원의 무기 - 프로그래머스 Lv.1

import java.util.*;

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        
        for(int i=1;i<=number;i++){
            int cnt = 0;
            for(int j=1;j*j<=i;j++){
                if(j*j==i) cnt++;
                else if(i%j==0) cnt+=2;
            }
            
            if(cnt > limit) {
                cnt = power;
            }
            
            answer += cnt;
        }
        
        return answer;
    }
}