#010 소인수분해

#문제)

자연수 N을 입력받아 소인수 분해하여 그 결과를 출력하는 알고리즘을 제시하라.

- 입력받은 정수 N이 2보다 작으면 알고리즘을 종료한다.

- 입력받은 정수 N이 소수이면 '소수'라고 출력한다.

- 입력받은 정수 N이 소수가 아니면 소인수 분해한 결과를 출력한다.

- 132는 2 X 2 X 3 X 11 과 같이 소인수 분해된다.

- 다양한 입력별 알고리즘의 실행 예시는 다음과 같다.

입력: 132 -> 출력: "2*2*3*11"

입력: 37 -> 출력: "소수"

입력: 20 -> 출력: "2*2*5"

입력: 0 -> 알고리즘 종료

소인수분해 할 결과를 저장 해야 하기 때문에 스택 사용이 필요하다.

그럼, 소인수분해 규칙을 살펴보자

먼저, 2부터 시작하여 N값을 %연산을 했을때 결과가 0인 경우, 2로 나눌 수 있는 수이기 때문에 나눈다.

스택에 2를 저장하고 반복하고, 2로 나누었을 때 나머지가 있다면 2를 +1 증가시킨다.

package dataStructure.prediction.problem;

import java.util.Scanner;

import java.util.Stack;

public class Factorization {

   

    private Scanner scanner = null;

    private Stack<Integer> factorizationStack = null;

   

    public Factorization() {

        // TODO Auto-generated constructor stub

        this.scanner = new Scanner(System.in);

        this.factorizationStack = new Stack<Integer>();

    }

   

    public void execute() {

        while(true) {

            System.out.println("please input number : (if you want to quit input '-1')");

            int command = scanner.nextInt();

            if(command == -1) {

                break;

            }

           

            if(isPrimeNumber(command)) {

                System.out.println("this number is prime number : "+command);

            }else {

                factorization(command);

            }

            print();

           

        }

        scanner.close();

    }

   

    private boolean isPrimeNumber(int num) {

        boolean isPrimeNumber = true;

        int v = 2;

        while(v < num) {

            if(num%v == 0) {

                isPrimeNumber = false;

                break;

            }

            v++;

        }

        return isPrimeNumber;

    }

   

    private void factorization(int num) {

        int v = 2;

        while(v <= num) {

            if(num%v==0) {

                num = num/v;

                factorizationStack.add(v);

            }else {

                //개선필

                v++;

            }

        }

    }

   

    public void print() {

        StringBuilder result = new StringBuilder();

        while(!factorizationStack.isEmpty()) {

            result.append(factorizationStack.pop());

            if(!factorizationStack.isEmpty()) {

                result.append("*");

            }

        }

        System.out.println(result.toString());

    }

   

    public static void main(String[] args) {

        // TODO Auto-generated method stub

       Factorization factorization = new Factorization();

       factorization.execute();

      

    }

}

*개선 필이라고 한부분은 소인수 분해이므로 굳이 1씩 증가할 필요없이 한단계 높은 소수로 올리면 되지만

소수를 모름. 그래서 isPrimeNumber할때 배열로 넣어놓을까 고민중