[백준] 11653번 : 소인수분해 _ JAVA ( 주석 설명 )

1번

( ⌜2581번 : 소수⌟에서 사용한 방법 )

→ '에라토스테네스의 채'를 이용한 소수 판별

- 저번 문제에서 사용한 '에라토스테네스의 채'를 한 번 이용해보고 싶어 작성해 보았다.

 

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


public class Main {
    public static boolean [] num_ary; //solve 함수에서 배열의 값이 정해지므로 static 으로 선언했다.

    //시간복잡도 : O(log(logN))
        //1. 입력받은 정수 범위까지 소수 판별
        //2. 소수만을 따로 추출
        //3. 입력받은 수를 소수만으로 따로 나누어, 떨어지는 수를 StringBuilder 에 저장
        //4. N이 1이 될 때까지 반복
        //5. 소인수분해 값 출력
    //공간복잡도 : O(N)
        //소수 판별을 위한 범위 정수 배열 + 소수만을 담은 배열
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //빠른 실행을 위해 버퍼를 이용해 입력을 받는다.

        int N = Integer.parseInt(br.readLine()); //소인수분해 할 정수를 입력받는다.

        num_ary = new boolean[N+1]; //입력받은 정수까지의 소수를 구하기 위한 범위 정수 배열

        solve(N); //소수 판별 함수 실행

        int[] prime = new int[N]; //소수만을 담은 배열

        int index = 0; //소수만을 집어 넣기 위해 생성한 변수
        for(int i=1;i<=N;++i){ //boolean 배열에서 소수인 부분만 따로 뽑아내, prime 배열에 집어넣는다.
            if(!num_ary[i]) {
                prime[index] = i;
                index++;
            }
        }

        StringBuilder sb = new StringBuilder(); //출력을 위한 StringBuilder 선언

        int i = 0; //소수만을 담은 배열의 변수
        while(N!=1){ //N이 소인수로 완전히 분해되어 1이 될 때까지 반복을 한다.
            while(prime[i]!=0){ //prime 배열의 default 값은 0으로, 저장된 소수 이후 값이 나올 때까지 반복한다.
                if(N%prime[i]==0){ //입력받은 N 이전의 소수로 나누어질 때
                    sb.append(prime[i]).append('\n'); //출력 StringBuilder 에 추가해준다.
                    N /= prime[i]; //N을 해당 소수로 나눈다.
                    i = 0; //똑같은 소수들의 곱이 나올수도 있으므로, 가장 작은 소수부터 계산을 다시 시작한다.
                }
                else //나누어지지 않았을 경우 다음 소수로 넘어간다.
                    i++;
            }
        }

        System.out.println(sb); //소인수분해 값 출력
    }

    //시간복잡도 : O(log(logN))
    //공간복잡도 : O(N)
    private static void solve(int num) { //num 까지 소수 찾기
        num_ary[0] = true; //0은 소수가 아니다. //입력 범위에 포함되지 않으나, 넣어보았다
        num_ary[1] = true; //1은 소수가 아니다.

        for(int i=2;i<=Math.sqrt(num);++i){ //sqrt(num)보다 큰 수일 경우 약수가 아니므로 검사할 필요가 없거나, 이전 약수와의 곱으로 소수가 아님을 알아낼 수 있으므로 검사할 필요가 없다.
            for(int j=i*i;j<=num;j+=i){ //에라토스테네스의 채 로 각각의 배수를 전부 지워낸다.
                num_ary[j] = true;
            }
        }
    }
}

 

---

 

2번

→ N+α 만큼 비교하여 소인수분해

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


public class Main {
    static StringBuilder sb = new StringBuilder();

    //시간복잡도 : O(N)
    //공간복잡도 : 자료구조 x
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); //소인수분해 할 정수 N을 입력받는다.

        solve(N); //소인수분해 함수 실행

        System.out.println(sb); //소인수분해 값 출력
    }

    //시간복잡도 : O(N)
    //공간복잡도 : 자료구조 x
    private static void solve(int num) {
        while(num>1){ //소인수분해가 완료될 때까지 반복한다.
            for(int i=2;i<=num;++i){ //2부터 차례대로 소인수분해를 시작한다.
                if(num%i==0) {
                    num/=i; //소인수를 찾으면 num 을 곧바로 나눠준다.
                    sb.append(i).append('\n'); //StringBuilder 출력에 더해준다.

                    i--; //큰 소수의 곱일 경우, 처음으로 돌아가 계산을 하는 반복을 줄여주기 위한 구문이다.
                }
            }
        }
    }
}

 

---

 

3번

→ 합성수, 소수의 성질을 이용한 소인수분해

- 이전에 공부했던 O(N)만큼의 반복이 아닌, O(sqrt(N))까지의 계산만으로 소수를 구하는 방식과 유사하다.

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


public class Main {
    //전체 시간복잡도 : O(sqrt(N))
    //전체 공간복잡도 : 자료구조 x
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); //소인수분해 할 정수 N을 입력받는다.

        solve(N); //소인수분해 함수 실행
    }

    //시간복잡도 : O(sqrt(N))
    //공간복잡도 : 자료구조 x
    private static void solve(int num) {
        //모든 수 num 은 곱셈으로 분해하면 sqrt(num)*sqrt(num)을 중심으로 대칭을 이루고 있다.
        //따라서 그 이후의 값은 앞뒤만 바뀔 뿐 똑같으므로 소인수를 구할 때 계산할 필요가 없다.
        //'에라토스테네스의 채'(?)처럼 2부터 차례대로 소수들이 나눌 수 있을 때까지 최대한 나누고 그 소인수들을 출력한다.
        for(int i=2;i<=Math.sqrt(num);++i){
            while(num%i==0){
                num/=i;
                System.out.println(i);
            }
        }

        //여기에서 num 이 제곱수가 아니면 나머지가 1로 완벽히 나누어 떨어지지 않는다.
        //이 수는 sqrt(num)보다 큰 수이고, 이 수로 num 을 나눈 수는 sqrt(num)보다 작은 수로 앞에서 이미 구한 소인수들의 곱이다.
        //따라서 이 수는 num 의 소수가 되므로 출력을 해준다. (num!=1일 경우)
        if(num!=1){
            System.out.println(num);
        }
    }
}