백준 11653: 소인수분해(C언어)

11653번: 소인수분해

문제

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

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

문제풀이

위의 내용을 정리해보면

1. N을 입력받는다.

2. N을 소인수분해를 하고 오름차순으로 출력한다.

 

정말 문제 자체는 간단하다. 소인수분해는 숫자 2부터 진행하기 때문에 2부터 N의 값과 나눠서 0이 나오는 경우라면 출력해주면 된다.

출력을 해주고 다음 체크를 하기 위해서 N을 나누고 다시 진행하면 된다. 이렇게 진행을 하면 어느순간 소인수분해가 안되는 값이 나온다.

소인수분해가 가능하지 않다는 것은 그 값이 소수이기 때문에 출력을 하고 N의 값을 1로 바꾼 후 while문을 탈출한다.

최종코드

#include<stdio.h>

int main() {
	int n = 0;
	scanf("%d", &n);
	while (n != 1) {
		int i = 2;
		for (i = 2; i * i <= n; i++) {
			if (n % i == 0) {
				printf("%d\n", i);
				n = n / i;
				break;
			}
		}
		if (i * i > n) {
			printf("%d\n", n);
			n = 1;
		}
	}
	return 0;
}