[알고리즘] 소인수분해 (Java)

소인수분해란?

소인수분해는 어떤 수 n을 더 이상 나눌 수 없는 소수(소인수)들의 곱으로 표현하는 것을 의미합니다. 예를 들어, 12는 더 이상 나눌 수 없는 소수인 2와 3의 곱으로 분해할 수 있습니다.

소인수란?

소인수란 어떤 수를 나누어떨어지게 할 수 있는 소수를 말합니다. 다시 말해, 소인수는 자신보다 작은 두 개의 자연수의 곱으로 나눌 수 없는 수입니다. 예를 들어, 2, 3, 5, 7 등이 소수이며, 어떤 자연수를 소수로 나누어 나머지가 0이 된다면 그 소수는 해당 수의 소인수입니다.

소인수분해 예시: 12

12를 소인수로 분해하는 과정은 다음과 같습니다:

1. 나눌 수 있는 가장 작은 소수인 2로 12를 나누면 6이 됩니다.
2. 다시 2로 6을 나누면 3이 됩니다.
3. 마지막으로 3을 나누면 1이 됩니다.

즉, 12 = 2 * 2 * 3이 됩니다.

코드 구현

다음은 소인수분해를 자바로 구현한 코드입니다:

public class Main {
    public static void main(String[] args) {
        int n = 12;
        
        factorize(n);
    }
    
    public static void factorize(int n) {
        while (n > 1) {
            for (int i = 2; i <= n; i++) {
                if (n % i == 0) {
                    System.out.print(i + " ");  // 한 줄에 소인수들을 출력
                    n /= i;
                    break;
                }
            }
        }
    }
}

코드 분석

• while 문: n이 1이 될 때까지 계속해서 소인수를 찾습니다. 이 반복문은 n이 소인수로 완전히 분해될 때까지 실행됩니다.
• for 문: 2부터 n까지의 수 중에서 n을 나누어떨어지게 하는 가장 작은 수(소인수)를 찾습니다. 이 반복문은 가능한 모든 소인수를 탐색하는 역할을 합니다.
• 조건문 if (n % i == 0): n이 i로 나누어떨어지면, i는 n의 소인수입니다.
  • 소인수 i를 출력하고, n을 i로 나누어 n의 값을 갱신합니다.
  • break를 사용해 현재 소인수를 찾으면, 다시 가장 작은 소인수를 찾기 위해 for 루프를 재시작합니다.

이 코드를 실행하면 12의 소인수들이 2 2 3 순서로 출력됩니다. 이는 12가 2 * 2 * 3으로 소인수분해되었다는 의미입니다.

추가 설명: 소인수분해의 중요성

소인수분해는 수학에서 매우 중요한 개념입니다. 특히, 소인수분해는 암호학, 정수론, 컴퓨터 과학 등 다양한 분야에서 활용됩니다. 예를 들어, 현대 암호 알고리즘은 매우 큰 수의 소인수분해가 어려운 성질을 이용하여 보안을 유지합니다.

또한, 소인수분해는 두 수의 최대공약수를 구하는 데도 유용합니다. 두 수를 각각 소인수분해한 후, 공통된 소인수를 찾아 곱하면 최대공약수를 쉽게 구할 수 있습니다.