[Java] 백준 풀기 11653 - 소인수분해

자바 백준 11653

브론즈 1

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

11653번: 소인수분해

 

 

 

 

 

문제 보기

분류: 수학, 정수론, 소수 판정

 

 

 

 

 

문제 풀기

소인수분해는 주어진 정수 N을 소수인 i로 나누며, 나눌 수 없을 때까지 반복한다. 이때, i는 2부터 제곱근까지 검사한다.

 

N이 1인 경우 바로 return 한다. for loop과 while loop을 통해 정수 N을 나누어 떨어지는 소인수 i를 모두 출력하고, 최종 남은 소인수를 출력한다.

 

 

 

 

 

코드 보기

import java.util.Scanner;

public class Main {

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

        primeFactorization(N);
    }
    
    // 소인수분해 함수
    private static void primeFactorization(int N) {
        // N이 1인 경우 아무것도 출력하지 않음
        if (N == 1) {
            return;
        }
        
        // N의 제곱근까지만 검사
        for (int i = 2; i * i <= N; i++) {
            // 정수 N을 i로 나눌 수 없을때까지 반복
            while (N % i == 0) {
                System.out.println(i);
                N = N / i;
            }
        }
        
        // 마지막 소인수 출력
        if (N > 1) {
            System.out.println(N);
        }
    }
    
}