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

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

11653번: 소인수분해

 

---

◎ 문제

 

 

---

◎ 코드

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // n 입력 받기
        double n = sc.nextDouble();
        // 소인수로 나누고 출력
        for (int i = 2; i <= n; i++) {
            // n을 i부터 나눈다.
            while (true) {
                // 만약 n을 i로 나눴을때 정수라면 값을 갱신하고 i를 출력한다.
                if((n/i)/1.0 == (int)n/i){
                    n = n/i;
                    System.out.println(i);
                }
                // 만약 아니라면 다음 i로 넘어간다.
                else{
                    break;
                }
            }
        }
    }
}

 

---

◎ 풀이 및 기록

 

의외로 엄청 오래걸린 문제다. 계산값이 정수인지 소수인지 구분하는걸 못해서....

추가로 소인수는 소수로 이루어지기 때문에 반복문 범위는 사실 n의 제곱근까지만 해도 된다. 근데 마지막에 남는 수가 제곱근보다 큰 소수일 수 있다. 문제를 푸는 동안에는 그걸 깨닫지 못하고 일단 맞추기 급급해 범위를 n까지 해버렸다. 마지막 n이 1이 아니면 출력해주면 되는데... 불필요한 연산을 줄이기위해 꼭 기억해둬야겠다.