[BOJ]백준 11653번: 소인수분해

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

문제

풀이

소인수를 구하는 문제이다.
풀이의 핵심은 어떤 수 N을 2개의 약수의 곱으로 표현할때, 두 수는 √N 보다 작은 수의 곱으로 나타낸 다는 것이다.

1. 정수 N이 주어지면, for문을 통해서 2 부터 루트 N번째 보다 작거나 같은 수로 나뉘는지 확인한다.
2. while문을 통해서, Number % i == 0 값이 되면, i는 소수이다.
3. Number를 i로 나누고 그 수를 Number에 저장해 반복한다.
4. 만약 소수인 수 17 같은 수를 입력하면, 2,3의 조건에 걸리는 것이 없으므로 Number != 1 인 경우를 생각해서 처리해준다.

소스코드

package baekjoon.solution;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Baekjoon_11653 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int Number = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for(int i=2;i<=Math.sqrt(Number);i++){
            while(Number % i ==0){
                sb.append(i).append("\n");
                Number = Number/i;
            }
        }

        if(Number != 1)
            sb.append(Number);


        System.out.println(sb);


    }
}

쉬울 줄 알았는데 생각보다 어려운 문제였던 것 같다.