[0단계/1점]순서쌍의 개수

어려웠음..

class Solution {
    public int solution(int n) {
        int answer = 0;
         for(int i=1; i*i<=n; i++){
             if(n%i==0){
                 answer++;
                if(i!=n/i){
                 answer++;
                }
             }
         }
        return answer;
    }
}

1️⃣ i * i <= n이 왜 필요한가?

우리는 어떤 숫자 n의 약수를 찾고 싶어.그런데 모든 약수는 짝을 이룬다!
즉, a * b = n인 (a, b) 약수 쌍이 존재해.

예를 들어, n = 20이라면:

• 1 * 20
• 2 * 10
• 4 * 5
• (5 * 4 부터는 중복이 시작됨!)
• (10 * 2, 20 * 1도 앞에서 이미 나왔어!)

💡 즉, 약수를 찾을 때 절반만 찾으면 돼!
반대쪽 약수는 자동으로 알 수 있거든

 

2️⃣ 왜 i * i <= n인가?

어떤 숫자 n이 있을 때, 그 숫자의 약수 중 최소 하나는 반드시 √n 이하야!
즉, i를 1부터 √n까지만 확인하면, 반대 약수(n / i)를 같이 찾을 수 있어!

예제: n = 20

• i = 1 → 1 * 20
• i = 2 → 2 * 10
• i = 4 → 4 * 5
• i = 5 → 5 * 4 (이제 중복이 시작됨! 멈춰도 됨!)

💡 즉, 5 이상부터는 볼 필요가 없어!

• 왜냐하면 반대 약수(n / i)로 이미 다 나왔기 때문이야.

즉, i가 √n을 넘어가면, 이미 모든 약수를 찾았으므로 중복이 시작됨!
그래서 i * i <= n까지만 검사하면 돼.

.

3️⃣ 예제별로 더 확인해보자!

(1) n = 36

√36 = 6, 즉 i는 6까지만 확인하면 된다!

i 값i * i 값n % i == 0 확인추가된 약수

1	1	36 % 1 == 0 ✅	1, 36
2	4	36 % 2 == 0 ✅	2, 18
3	9	36 % 3 == 0 ✅	3, 12
4	16	36 % 4 == 0 ✅	4, 9
5	25	36 % 5 == 0 ❌	-
6	36	36 % 6 == 0 ✅	6, 6 (중복)
7 이상	49 > 36	(반복 종료)	-

💡 중복되는 6,6을 제외하면 약수는 9개!
즉, i * i <= n까지만 확인하면 모든 약수를 찾을 수 있어.