[JAVA] 백준 알고리즘 11653번 소인수 분해

www.acmicpc.net/problem/11653

11653번: 소인수분해

소수는 약수로 1과 자기 자신만을 가지는 수를 소수라 한다.

예를 들어 자연수 N이 있다고 하자. N의 약수는 1과 N밖에 없을때 자연수 N을 소수라 한다.

 

특정한 수를 소인수분해 한다는 것은 위와 같은 소수들의 조합으로 수를 나타내는 것을 뜻한다.

108을 예시로 들면 108은 2^2*17로 나타낼수 있는데 이것을 소인수분해라 한다.

 

이러한 소인수분해 알고리즘을 짜게되면 이런식으로 된다.

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int num = sc.nextInt();
		int prime = 2;

		while (num >= prime) {

			if (num % prime == 0) {
				//식1
				System.out.println(prime);
				
				num = num / prime;
				
			} else {
				//식2
				prime++;
				
			}

		}

	}

}

num은 입력받은 수를 저장하기 위한 변수고 prime은 num을 나누기 위한 int형 변수이다. (prime의 초기값이 2인 이유는 소수가 2부터 시작해서이다.)

 

while문의 조건식을 보게되면 입력받은 수가 나누는 수보다 크거나 같을때만 반복하게 되는데 num과 prime이 같으면 num은 소수가 되고 prime이 크게되면 자연수가 아니게되기 때문에 조건식은 저렇게 된다.

 

반복문 내부에 있는 조건문은 num을 prime으로 나눈 나머지가 0일때 prime을 출력하고 num에 num을 prime으로 나눈 값을 저장하게 된다.

나눈 나머지값이 0이 아닐때는 prime에 1을 더한다.

 

처음 위 코드를 봤을때 한가지 의문이 생길수도 있다.

나머지가 0이 아닐때 식2 부분을 보면 "prime에 1을 더하게 되는데 초기값인 2일때는 1을 더해도 3이 되는데 1이 증가되면 4기 때문에 소수로 나눠야하는 소인수분해가 아니지 않나?" 하는 생각이 들 수 있다.

 

위 의문의 해답은 4로 나눠지는 수는 그 전의 조건인 2로 나눌때 이미 나눠졌어야 하기때문에 prime이 1씩 증가하더라도 상관이 없어진다. 4뿐만 아니라 6, 8, 9, 10과 같은 수들은 2, 3, 5의 배수로 이뤄져있기 때문에 그전에 나눠져 num의 값이 변하면 소수가 아닌 수들의 배수일 수는 없어진다.