백준 11653 소인수 분해 (JAVA 자바 풀이)

백준 11653 소인수 분해 (JAVA 자바 풀이)

 

---

 

 

 

📌 문제 

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

 

 

⚔ 입력

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

 

 

📣 출력

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

 

 

 

 

---

 

 

 

💎 문제 분석

 

 

N의 최대값이 10,000,000에 시간제한은 1초이므로 반복문을 사용하면 100% 시간 초과가 날 것이고 

일일히 구하는 것이 아니라 숫자를 줄여나가면서 구하면서 출력하는 방식으로 풀어야 한다. 

 

 

 

💡 코드 구현

 

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

public class Main {

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

		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		int number = Integer.parseInt(stringTokenizer.nextToken());

		printOutPrimeFactors(number);
	}

	private static void printOutPrimeFactors(int number) {
		int primeFactor = 2;
		while( number !=1) {
			if (number %primeFactor ==0){
				System.out.println(primeFactor);
				number = number / primeFactor;
				continue;
			}
			primeFactor++;
		}
	}

}