[백준/JAVA] 11653 : 소인수분해 ( 기본 수학 2 )

문제

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

입력

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

출력

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

 

예제입력	예제출력
72	2 2 2 3 3
3	3
6	2 3
2	2
9991	97 103

 

⭕ 풀이

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int input = Integer.parseInt(br.readLine());
        br.close();
        StringBuilder sb = new StringBuilder();
        
        while(input>1){
            for(int i=2;i<=input;i++){
                if(input%i==0){
                    sb.append(i).append("\n");
                    input /= i;
                    break;
                }
            }
        }
        System.out.print(sb.toString());
    }
}

✅ 입력받은 수를 i로 나눈 나머지가 0이라면 i를 append한뒤 입력받은수를 i로 나누고 break;

이를 반복하며 while문의 조건이 false가 되면 sb를 출력하는데

입력받은수가 1이라면 처음부터 만족하지못하므로 StringBuilder sb 에는 아무것도 들어가지않는다.

 

 

✅ 다른분의 풀이참조

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

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        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);
    }
}

이게 무슨식이지 하고 생각했었는데 입력받은수의 제곱근을 i로 나누었다.

특정 수의 제곱근까지 둘러보았는데 나누었을때 0 이 되는수가 없다면 해당수는 그자체로 소수인 수이다..

예제인 9991로 예를들면 9991의 제곱근은 99.95498987044118이 나오는데

여기서 나누었을때 나머지가 0이되는 수가 있는지는 99 까지만 찾아보면 된다는 뜻이된다.

결국 97로 나누었을때 나머지가 0 이 되었고

input은 103이 되었는데 103의 제곱근은 10.14889156509222 인데

이미 i가 10을 넘어있는 상태이므로 for문이 끝나고 나가 if문으로 간다

103 != 1이므로 103도 sb에 append 해준다.

 

 

 

-출처

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