[BOJ / java] 11653 : 소수분해

[BOJ / java] 11653 : 소수분해

https://www.acmicpc.net/problem/11653

 

 

 

 

📚 Table of Contents

• 문제
• 입력
• 출력
• 예제
  • 예제 입력 1
  • 예제 출력 1
  • 예제 입력 2
  • 예제 출력 2
• 문제 풀이
  • 코드 설명:
  • 코드의 동작 방식:
  • 코드의 핵심 부분:
  • 코드의 흐름:
  • 풀이

 

 

 

 

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

 

 

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

 

 

예제

예제 입력 1

72

예제 출력 1

2
2
2
3
3

 

예제 입력 2

3

예제 출력 2

3

 

 

 

 

문제 풀이

코드 설명:

이 코드는 주어진 숫자를 소인수분해하여 모든 소인수를 출력하는 프로그램입니다.

 

 

코드의 동작 방식:

1. 표준 입력으로부터 정수 n을 입력받습니다.
2. 2부터 시작하여 n의 제곱근까지 반복하면서 n을 나누는 소인수를 찾습니다.
3. 소인수로 나눌 때마다 해당 소인수를 출력하고 n을 갱신합니다.
4. 반복문이 끝난 후 n이 1보다 크면 남은 소인수를 출력합니다.

 

 

코드의 핵심 부분:

1. 2부터 n의 제곱근까지의 숫자들로 n을 나누며 소인수 분해.
2. 소인수로 나눌 때마다 결과를 출력하고 n을 갱신.
3. 반복문 후 남은 n이 1보다 크면 그 값을 출력.

 

 

코드의 흐름:

입력 → 제곱근까지 반복하며 소인수 분해 → 남은 값 출력

 

 

풀이

    

    
    
    
    
    
import java.io.*;

public class _06_소인수분해 {
    public static void main(String[] args) throws IOException {
        // BufferedReader를 사용하여 표준 입력을 받습니다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 정수 n을 입력받아 정수로 변환합니다.
        int n = Integer.parseInt(br.readLine());

        // 2부터 n의 제곱근까지 반복하면서 소인수를 찾습니다.
        for (int i = 2; i * i <= n; i++) {
            // n이 i로 나누어 떨어질 때까지 반복합니다.
            while (n % i == 0) {
                // i를 출력하고 n을 i로 나눕니다.
                System.out.println(i);
                n /= i;
            }
        }

        // 반복문이 끝난 후 n이 1보다 크면 남은 소인수를 출력합니다.
        if (n > 1) {
            System.out.println(n);
        }
    }
}