[백준 알고리즘] 4149. 큰 수 소인수분해

큰 수 소인수분해

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	1050	105	42	11.699%

문제

큰 수를 소인수 분해 해보자.

입력

입력은 한 줄로 이루어져 있고, 소인수 분해 해야 하는 수가 주어진다. 이 수는 0보다 크고, 262보다 작다.

출력

입력으로 주어진 양의 정수를 소인수 분해 한 뒤, 모든 인수를 한 줄에 하나씩 증가하는 순서로 출력한다.

예제 입력 1 복사

 
18991325453139

예제 출력 1 복사

 
xxxxxxxxxx
3
3
13
179
271
1381
2423

 

 

---

 

풀이

 

나는 소인수를 계산하면서 인수가 나올 때 마다 바로바로 출력을 해주는 식으로 소스를 작성했다.

배열을 만들어주어서 배열에 차곡차곡 넣은 후, 배열을 순서대로 출력해 주어도 된다.

 

 
​x
import java.util.Scanner;
​
public class bj4149 {
​
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        System.out.print("n = ");
        long n = sc.nextLong();
        
        while (n > 1) {
            
            for (int i = 2; i <= n; i++) {
                
                if (n % i == 0) {
                    System.out.println(i);
                    n = n / i;
                    
                    break;
                }
            }
        }
        
        sc.close();
    }
​
}