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

소인수분해란?

내 풀이

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// 정수 N이 주어졌을 때, 소인수분해하는 문제

		// 1. 테스트케이스 int를 받아온다.
		// 2. 소수를 넣어줄 변수를 새로 만들어준다.
		// 3. while문안에 for문을 돌려서 num을 나눠줄 i가 소수인지 먼저 구한다.
		// 4. 그 후, i가 소수이면서 num의 약수일 때 prime에 i를 넣어주고 소인수분해한다.
		// 5. num이 prime보다 작아지면 그대로 break한다.

		Scanner sc = new Scanner(System.in);
		StringBuffer sb = new StringBuffer();

		int num = sc.nextInt();
		int prime = 0;

		while (true) {
			for (int i = 2; i <= Math.sqrt(num); i++) {
				// i의 소수를 구하는 for문
				boolean flag = true;
				for (int j = 2; j < i; j++) {
					if (i % j == 0) {
						flag = false;
					}
				}
				// i가 소수이면서 num의 약수이면 실행하겠다.
				if (num % i == 0 && flag == true) {
					prime = i;
					num = num / prime;
					sb.append(prime);
					sb.append('\n');
					break;
				}
			}

			if (num <= prime) {
				break;
			}
		}
		System.out.println(sb.toString());
	}
}

느낀점

어떤 자연수 N이 있을 때, N의 제곱근까지만 나누어 보면 소인수분해가 가능합니다.

그래서 첫 for문을 num까지 주지 않고, Math.sqrt()메서드를 이용했다. Math.sqrt()는 제곱근을 구해주는 메서드이다.

근데 이렇게 했는데도 틀렸다.. 또 시간초과… 한 시간을 고민하다 결국 답을 찾아봤다. 아주 허무하다.