유랑하는 개발자

정보처리기사 / 정보처리산업기사 실기시험 알고리즘의

Section012 - 소인수 분해하기

입력받은 수(B)를 소인수 분해 하기 위해서는,

2부터 B의 제곱근 까지 나누어 떨어지는가를 확인 해야 합니다.

결과 값에 출력된 결과를 보며 로직을 이해 하세요!

Section012.java

public class Section012 {

	public static void main(String[] args) {
		int[] A = new int[100];
		int B = 20;
		int C = 0; // 배열 내 소인수 저장 위치
		int D = 2; // 제수 저장 변수(피제수를 2부터 나눔)
		int E; // 입력 받은 수(B)의 제곱근이 저장될 변수
		int MOK = 0;
		int NMG = 0;
		int i;

		while (true) {
			E = (int) Math.sqrt(B); // B의 제곱근을 E에 저장
			System.out.println("입력 받은 수 = " + B + ", 제곱근 E=" + E);
			while (true) {
				System.out.println("제수 D=" + D + ", 제곱근 E=" + E);
				if (D > E) {	// 제수(D)가 피제수 제곱근(E) 보다 크면 소인수
					D = B;
					System.out.println("break:" + D);
					break;
				} else {
					MOK = B / D;
					NMG = B - MOK * D;
					System.out.println(B + "/" + D + " NMG=" + NMG);
					if (NMG != 0) {
						D = D + 1;
						continue;
					} else
						break;
				}
			}

			System.out.println("소수 = " + D);
			A[C] = D;
			C = C + 1;	// 배열의 위치 증가
			if (B == D) {
				System.out.println("End.....");
				for (i = 0; i < C; i++)
					System.out.print(A[i] + " ");
				System.out.println("");
				break;
			} else {
				B = MOK;
				continue;
			}
		}
	}
}

결과 값

입력 받은 수 = 20, 제곱근 E=4
제수 D=2, 제곱근 E=4
20/2 NMG=0
소수 = 2
입력 받은 수 = 10, 제곱근 E=3
제수 D=2, 제곱근 E=3
10/2 NMG=0
소수 = 2
입력 받은 수 = 5, 제곱근 E=2
제수 D=2, 제곱근 E=2
5/2 NMG=1
제수 D=3, 제곱근 E=2
break:5
소수 = 5
End.....
2 2 5