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

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

11653번: 소인수분해

---

---

참고 유형

https://unknownomad.tistory.com/147

[백준] 1978번 : 소수 찾기 - Java

---

소인수분해

• 어떤 수를 소수인 인수로 분해하는 것

---

알고리즘

1. 반복문의 범위 : √N

• 어떤 N을 두 개 이상의 곱셈(인수)으로 표현할 때 인수 중 한 개 이상은 반드시 √N보다 작거나 같음

 

2. N /= i 작업 후 남은 최종 N 처리 문제

N = 34 일 때
√N ≒ 5.83
for 반복문의 i가 2 ~ 5까지 반복 후 종료되면
N은 17이라는 인수를 가지고 있으나 출력하지 못한 채 종료되어버림
∴ for 반복문 종료 후 N != 1 이면 N = 소수이자 인수 ➡ 한 번 더 출력해주자

---

구현 방법

1. Scanner + System.out.println()
2. Scanner + StringBuilder
3. BufferedReader + StringBuilder

---

풀이

1. Scanner + System.out.println()

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
    
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
 
        for (int i = 2; i <= Math.sqrt(N); i++) { //or i * i <= N
            while (N % i == 0) {
                System.out.println(i);
                N /= i;
            }
        }
        if (N != 1) {
            System.out.println(N);
        }
    }
}

 

2. Scanner + StringBuilder

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
    
        Scanner in = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int N = in.nextInt();
 
        for (int i = 2; i <= Math.sqrt(N); i++) { //or i * i <= N
            while (N % i == 0) {
                sb.append(i).append('\n');
                N /= i;
            }
        }
        if (N != 1) {
            sb.append(N);
        }
        System.out.println(sb);
    }
}

 

3. BufferedReader + StringBuilder

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
    public static void main(String[] args) throws IOException {
    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
 
        for (int i = 2; i <= Math.sqrt(N); i++) {
            while (N % i == 0) {
                sb.append(i).append('\n');
                N /= i;
            }
        }
        if (N != 1) {
            sb.append(N);
        }
        System.out.println(sb);
    }
}

---

성능

1. BufferedReader + StringBuilder
2. Scanner + StringBuilder
3. Scanner + System.out.println()

 

---

출처 : https://st-lab.tistory.com/152