[Java]백준 #11653 소인수분해

11653번: 소인수분해 (acmicpc.net)

11653번: 소인수분해

[문제]

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

---

소인수분해 : 자연수를 소인수들의 곱으로 나타낸 것

어떤 수가 주어졌을 때 그 수를 소인수, 즉 소수인 인수들로 나타내는 것이다.

 

우선 입력하는 자연수 N이 어떤 수이냐에 따라 동작을 다르게 했다.

만약 N이 소수라면, 소인수가 없이 그 자체로 소수이므로 N을 그대로 출력하면 되고,

N이 합성수라면 소인수분해하여 소인수들을 출력하도록 했다.

 

package lv9;

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

public class No11653 {
	static boolean PNumber(int num) {
		int rnum = (int)Math.sqrt(num);
		if(num==1) {
			return false;
		}
		for(int j=2;j<=rnum;j++) {
			if(num%j==0)
				return false;
		}
		return true;
	}
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int a=2;
		
		if(PNumber(n)) {
			System.out.println(n);
		}
		else {
			while(n>1) {
				if(PNumber(a)==false)
					a++;
				
				if(n%a==0) {
					System.out.println(a);
					n/=a;
				}
				else {
					a++;
				}
			}
		}
	}

}

먼저 앞선 문제들에서 이용했던 소수판별 함수를 정의했다.

 

메인함수에서 n을 입력받는다. a는 n의 소인수를 저장하는 변수이며 가장 작은 소수인 2로 초기화해두었다.

 

먼서 if문에서 PNumber(n)을 통해 n이 소수인지 아닌지 판별한다.

 

n이 소수가 아니라면 소인수분해 과정을 진행한다.

소인수분해는 n을 소인수로 계속 나누어 1이 될때까지 반복하도록 while문을 설정한다.

a가 n이하의 소수가 될 수 있도록 PNumber(a)를 통해 소수판별을 하고, 만약 소수가 아니라면 소수가 될때까지 증가시킨다.

a에 소수가 저장되었다면, n%a==0 의 조건을 통해 a가 n의 소인수인지 아닌지 판별한다.

만약 나누어 떨어지면 a는 n의 소인수이므로 a값을 출력하고, n을 a로 나누어준다.

만약 나누어 떨어지지 않으면 a는 n의 소인수가 아닌 소수이므로 a값을 증가시켜 다음 소수를 저장할 수 있도록 한다.