[JAVA] 8. 필수 알고리즘 Ⅶ. 소인수분해

❗

1보다 큰 자연수를 소인수(소수인 인수)들만의 곱으로 나타내는 것 또는 합성수를 소수의 곱으로 나타내는 방법

1. 60을 소인수분해 해보자

1. 진행 상황 작성

package algo;

public class PrimeFactor {
    public static void main(String[] args) {
        // 소인수 분해
        int n = 60;
        System.out.println(60 / 2 + "<-몫 2의1승 나머지->" + 60 % 2);
        System.out.println(30 / 2 + "<-몫 2의2승 나머지->" + 30 % 2);
        System.out.println(15 / 2 + "<-몫 2의3승 나머지->" + 15 % 2);
        System.out.println(15 / 3 + "<-몫 3의1승 나머지->" + 15 % 3);
        System.out.println(5 / 3 + "<-몫 3의2승 나머지->" + 5 % 3);
        System.out.println(5 / 5 + "<-몫 5의1승 나머지->" + 5 % 5);
        // 몫이 1이고 나머지가 0이면 끝
    }
}

2. 진행 상황 패턴 분석

예시 n = 60; 나누는수 = 2; 나누는수의 승 = 0;

60 - 2 - 0
⬇️
30 - 2 - 1
⬇️
15 - 2 - 2
⬇️
15 - 3 - 0 -> 나누는수 2 저장, 나누는수의 승 2 저장 / 나누는수 up, 나누는수의 승 0 초기화
⬇️
5 - 3 - 1
⬇️
5 - 5 - 0 -> 나누는수 3 저장, 나누는수의 승 1 저장 / 나누는수 up, 나누는수의 승 0 초기화
⬇️
1 - 5 - 1
⬇️
1 - 9 - 0 -> 나누는수 5 저장, 나누는수의 승 1 저장 / 나누는수 up, 나누는수의 승 0 초기화

n = 1 이고 나누는수의 승이 0 이니 그만 계산

3. 패턴을 코드로 작성

package algo;

import java.util.List;
import java.util.ArrayList;

public class PrimeFactor01 {
    public static void main(String[] args) {
        int n = 60;
        int 나누는수 = 2;
        int 승수 = 0;
        List<Integer> 나누는수list = new ArrayList<>();
        List<Integer> 승수list = new ArrayList<>();

        if (n % 나누는수 == 0) {
            n = n / 나누는수;
            승수++;
        } else {
            if (승수 != 0) {
                승수list.add(승수);
                나누는수list.add(나누는수);
                나누는수 = 나누는수 + (n % 나누는수);
                승수 = 0;
            } else {
                나누는수 = 나누는수 + (n % 나누는수);
            }
        }
    }
}

4. 패턴을 반복

package algo;

import java.util.ArrayList;
import java.util.List;

public class PrimeFactor {
    public static void main(String[] args) {
        int n = 45;
        int 나누는수 = 2;
        int 승수 = 0;
        List<Integer> 나누는수list = new ArrayList<>();
        List<Integer> 승수list = new ArrayList<>();


        while (true) {
            if (n % 나누는수 == 0) {
                n = n / 나누는수;
                승수++;
            } else {
                if (승수 != 0) {
                    승수list.add(승수);
                    나누는수list.add(나누는수);
                    나누는수 = 나누는수 + (n % 나누는수);
                    승수 = 0;
                } else {
                    나누는수 = 나누는수 + (n % 나누는수);
                }
                if (n == 1) break;
            }
        }
        System.out.println("나누는수 배열 = " + 나누는수list.toString() + ", 승수 배열 = " + 승수list.toString());
    }
}

5. 결과 도출

package algo;

import java.util.ArrayList;
import java.util.List;

public class PrimeFactor {
    public static void main(String[] args) {
        int n = 60;
        int NUMBER = n;
        int 나누는수 = 2;
        int 승수 = 0;
        List<Integer> 나누는수list = new ArrayList<>();
        List<Integer> 승수list = new ArrayList<>();


        while (true) {
            if (n % 나누는수 == 0) {
                n = n / 나누는수;
                승수++;
            } else {
                if (승수 != 0) {
                    승수list.add(승수);
                    나누는수list.add(나누는수);
                    나누는수 = 나누는수 + (n % 나누는수);
                    승수 = 0;
                } else {
                    나누는수 = 나누는수 + (n % 나누는수);
                }
                if (n == 1) break;
            }
        }

        System.out.print(NUMBER + " = ");
        for (int i = 0; i < 나누는수list.size(); i++) {
            System.out.print(나누는수list.get(i) + "의" + 승수list.get(i) + "승");
            if (i == 나누는수list.size() - 1) break;
            System.out.print(" X ");
        }
    }
}

6. 테스트 숫자 변경

package algo;

import java.util.ArrayList;
import java.util.List;

public class PrimeFactor {
    public static void main(String[] args) {
        int n = 50;
        int NUMBER = n;
        int 나누는수 = 2;
        int 승수 = 0;
        List<Integer> 나누는수list = new ArrayList<>();
        List<Integer> 승수list = new ArrayList<>();


        while (true) {
            if (n % 나누는수 == 0) {
                n = n / 나누는수;
                승수++;
            } else {
                if (승수 != 0) {
                    승수list.add(승수);
                    나누는수list.add(나누는수);
                    나누는수 = 나누는수 + (n % 나누는수);
                    승수 = 0;
                } else {
                    나누는수 = 나누는수 + (n % 나누는수);
                }
                if (n == 1) break;
            }
        }

        System.out.print(NUMBER + " = ");
        for (int i = 0; i < 나누는수list.size(); i++) {
            System.out.print(나누는수list.get(i) + "의" + 승수list.get(i) + "승");
            if (i == 나누는수list.size() - 1) break;
            System.out.print(" X ");
        }
    }
}