[BackJoon]11653번

문제

 

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

 

입력

 

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

 

출력

 

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

 

풀이

 

이전 글에 적은 문장에 덧붙여, 소인수분해에도 왕도가 없다.

 

해서 아무렇게나 짜도 괜찮겠지~ 하고 코드를 짜다가 세 시간 정도를 날리고

 

두 번 정도 코드를 근본적으로 갈아엎었다.

 

로직은 단순한데 시간초과에 자꾸 걸려서 일단 스트림과 리스트를 버리고,

 

AKS 알고리즘을 구현해 보려다 실패하고,

 

리만 함수에 대해 읽다가 정신을 차렸다.

 

해서 간단하게 에라토스테네스의 체를 이용해 순회하면서 소인수가 나오면 그때그때 출력하도록 만들었다.

 

2부터 시작해서 더 이상 2로 나누어 떨어지지 않을 때까지 주어진 숫자를 나누고 다음은 3으로, 4는 2의 배수니까 바로 넘어갈 테고..

 

하는 식으로 코드를 짜고 다른 분의 코드를 참고하려고 하니 거의 비슷한 모양이 나와있어서 좀 멋쩍었다.

import java.util.Scanner;

public class Prob11653_3 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        for (int i = 2; i <= Math.sqrt(n); i++) {

            while (n % i == 0) {
                System.out.println(i);
                n /= i;
            }
        }
        if (n != 1) System.out.println(n);
    }
}