[실기] 13. 소인수 분해

in 정보처리기사 on 기사 실기 알고리즘


소인수 분해


설명

  • 소인수분해란? 자연수를 소인수들의 곱으로 표현한 것
  • 12의 약수(인수)는 1, 2, 3, 4, 6, 12이다. 인수 중에 소수인 것들을 소인수라고 말한다.


문제

  • 자연수 N을 입력받아 소인수 분해하여 그 결과를 출력하는 알고리즘을 제시하라
    • 자연수 N은 1000이하의 자연수이다.
    • 자연수 N은 2보다 작으면 알고리즘 종료, 소수이면 “소수” 출력을 한다.


문제공략

  • 1 . 입력받은 자연수 N을 2부터 순차적으로 나눈다.
  • 2 . 나누어진 몫을 다시 2부터 나눈다.
  • 위의 1, 2를 루틴해서 소인수분해를 구한다.


JAVA

import java.util.*;
import java.io.*;

class Main {
	public static void main (String[] args) {
	    Scanner in = new Scanner(System.in);
		int A[] = new int[20];
		int N = in.nextInt();
		int T = 0;
		
		do {
		    if (N >= 2) {
		        int P=2;
		        for (; P<=N; P++) {
		            if (N % P == 0) break; 
		        }
		        A[T] = P;
		        N = N / P;
		        T++;
		    } else {
		        return;
		    }
		} while (N != 1);
		
		if (T == 1) {
		    System.out.println("소수");
		} else {
		    for (int J=0; J<T-1; J++) {
		        System.out.println(A[J] + "*");
		    }
		}
		System.out.println(A[T-1]);
	}
}