백준 11653번: 소인수분해

처음 풀이

package BOJ.step9;

import java.util.Scanner;

public class BOJ11653 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();


        for (int i = 2; i <= N; i++) {
            while (N % i == 0) {
                System.out.println(i);
                N = N / i;

            }
        }
    }
}

코드의 실행 시간이 오래 걸리는 이유는 불필요하게 큰 숫자까지 반복문을 실행하기 때문이다. 이를 개선하는 방법을 설명하겠다.

---

문제 분석

BOJ11653(소인수분해) 문제에서는 자연수 ( N )을 소인수분해하여 출력해야 한다.

현재 코드의 비효율적인 부분:

• for 루프가 i = 2부터 N까지 모든 수를 검사한다.
• 즉, ( N )이 소수라면 끝까지 반복문을 실행해야 한다.

---

개선 방법

✅ 1. 반복 범위를 줄이기

• 어떤 수의 약수는 제곱근 이하에 존재한다.
• 따라서, 반복문의 범위를 ( \sqrt{N} )까지로 줄일 수 있다.

✅ 2. 소수 판별을 더 빠르게 하기

• 2부터 시작하여 소인수를 나누면서, ( N )이 1이 되면 반복을 종료할 수 있다.

---

개선된 코드

package BOJ.step9;

import java.util.Scanner;

public class BOJ11653 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        // 2부터 sqrt(N)까지 확인
        for (int i = 2; i * i <= N; i++) {
            while (N % i == 0) {
                System.out.println(i);
                N /= i;  // N을 i로 나누어 갱신
            }
        }

        // 남은 수가 1보다 크다면 그 자체가 소수이므로 출력
        if (N > 1) {
            System.out.println(N);
        }

        sc.close();
    }
}

---

💡 모든 약수는 "짝"을 이루고 있다!
예를 들어 36의 약수를 생각해보자.

• 1 × 36
• 2 × 18
• 3 × 12
• 4 × 9
• 6 × 6 ← 여기서 멈춤! 🎯
• (뒤쪽은 앞에서 찾은 약수의 짝이므로 필요 없음)

✅ 제곱근(6)까지만 찾으면, 나머지는 자동으로 구할 수 있다!

---

📌 뒤쪽 값들이 필요 없는 이유

약수를 구할 때 작은 숫자로 먼저 나누면, 자동으로 큰 숫자도 구할 수 있다!

예를 들어, 36을 나누는 과정:

1. 2로 나누면 18이 남음 → 18도 약수!
2. 3으로 나누면 12가 남음 → 12도 약수!
3. 4로 나누면 9가 남음 → 9도 약수!
4. 6으로 나누면 6이 남음 → 6도 약수!

💡 이미 작은 숫자로 나누면서 큰 숫자도 자동으로 구해진다!
💡 그래서 제곱근까지만 검사해도 충분하다! 🚀

---

📌 다른 예제: 100의 약수

• 1 × 100
• 2 × 50
• 4 × 25
• 5 × 20
• 10 × 10 ← 여기서 멈춤! 🎯

✅ 제곱근(10)까지만 보면, 나머지는 자동으로 따라온다!

---