백준 11653번 (소인수분해) c언어

문제

11653번: 소인수분해

어떤 정수 n이 주어졌을때, n을 소인수분해 하는 과정을 전부 출력해주면 된다.

예를들어 만약에 정수 n 이 100이면  우리는 100을 소인수분해 하는 과정

즉, (보라색 동그라미)2, 2, 5, 5를 출력해주면 된다.

void soin(int a) {  //소인수분해
	for (int i = 2; i * i <= a; i++) {
		if (a % i)
			continue;
		while (a % i==0) {
			printf("%d\n", i);
			a /= i;
		}
	}
	if (a != 1) {
		printf("%d\n", a);
	}
}

먼저 for문에서 정수 n을 받게 되면 n의 제곱근까지 n과 나누어 질 수 있는지 확인하면 된다.

if(a % i) 만약 n이 i와 나눠서 나머지가 0이 아니면 나누어 떨어질 수 없으므로 continue한다.

while(a % i) 만약 a가 i와 나누어 떨어지면 바로 i를 출력해주고 또 다시 i와 나눈다. 이를 반복한다.

if(a != 1) 만약 a가 1이면 완전히 소인수분해가 끝난것이므로 if문으로 안들어가게 된다. 

아까 그림에서 봤다시피 소인수분해가 끝나고 1은 출력해줄 필요가 없기 때문이다.

전체 코드는 다음과 같다.

#include<stdio.h>
void soin(int a) {  //소인수분해
	for (int i = 2; i * i <= a; i++) {
		if (a % i)
			continue;
		while (a % i==0) {
			printf("%d\n", i);
			a /= i;
		}
	}
	if (a != 1) {
		printf("%d\n", a);
	}
}
int main() {
	int n;
	scanf("%d", &n);
    
	soin(n);
    
	return 0;
}