[JAVA] 11653번 - 소인수분해

[JAVA] 11653번 - 소인수분해

출처 - https://www.acmicpc.net/problem/11653

문제

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

입력

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

출력

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

예제 입력 1 72 예제 출력 1 2 2 2 3 3

예제 입력 2 3 예제 출력 2 3

예제 입력 3 6 예제 출력 3 2 3

예제 입력 4 2 예제 출력 4 2

예제 입력 5 9991 예제 출력 5 97 103

< 소스 코드 >

import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(br.readLine()); for(int i=2; i<=Math.sqrt(n); i++){ while(n % i == 0){ bw.write(i + "

"); n /= i; } } if(n != 1) bw.write(n +"

"); bw.flush(); bw.close(); br.close(); } }

이 문제는 소인수분해를 구하는 문제 이다. 소인수분해는 우리가 흔히 수학적으로 풀었을 때 간단히 할 수 있었다.

하지만 막상 코드로 작성해보려고 하니, 약간 주의해야될 것도 있었다.

그냥 간단하게 n과 나누어 떨어지는 수를 찾기 위해 2부터 주어진 수 n까지 for문으로 반복하면서 출력하는 방식이 있는데, 이는 솔직히 효율적이지 못하다.

그래서 for문을 반복하는데, 저번에 1978번 - 소수 찾기처럼 자연수 n의 제곱근을 구하고 그 범위 안에서만 반복 하는 것이다. 범위가 훨씬 좁아지기 때문에 더 효율적이게 n과 나누어 떨어지는 수를 찾을 수 있다.

여기서 주의해야 할것은, 만약에 17을 입력했다고 한다면, 17의 제곱근이 4.xxxx이므로 2 ~ 4까지 반복하여 실행한다.

하지만 2 ~ 4까지 17과 나누어 떨어지는 수를 찾을 수 없기 때문에 while문, for문이 종료되고

또한, 출력도 하지 못한채 프로그램이 종료된다.

그렇기 때문에 마지막에 출력할 수가 남아 있기 때문에 if문을 통해 수를 출력 해야한다.

from http://puzzle-moon.tistory.com/87 by ccl(A) rewrite - 2021-12-30 14:27:10