[Java] 백준알고리즘 #11653 소인수분해

백준알고리즘 #11653 소인수분해 문제

입력받은 수에 대해서 소인수분해를 하여 각 소인수들을 출력하는 문제이다.

https://blog.naver.com/soojongzzang/222024980958

소인수분해는 위와 같이 소수를 이용하여 가장 작은 소수부터 본래의 수를 나누어

더이상 나누어 떨어지지 않는 수(소수)가 나올 때 까지 나누면 된다.

위의 경우 80을 차례대로 나눈 결과가 2,2,2,2,5가 나오므로 이것이 소인수분해 결과가 된다.

위 그림을 참고하여 이 문제를 해결해보자.

먼저 본래의 수를 n, 나누는 수를 i라고 하자.

i는 소수중 가장 작은숫자인 2부터 시작한다.

int n;
int i = 2;

 

 

이 i는 차례로 커져가면서 n을 나누는데 나누어 떨어진다면 그 i는 소인수가 될 것이고 아니라면 i값을 1씩 증가시킨다.

if문을 사용해 나누어 떨어진다면 n에서 i를 나누고, i를 출력한 후 i를 2로 초기화해준다.

아니라면 i값을 1씩 증가시킨다.

if(n % i == 0){
	n = n / i;
	System.out.println(i);
	i=2;
} else i++;

 

 

 

 

전체 코드를 보면

import java.util.Scanner;

public class Test {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int i = 2;

		while (n != 1) {
			if (n % i == 0) {
				n = n / i;
				System.out.println(i);
				i = 2;
			} else
				i++;

		}

	}

}