[C] 백준 11653번 : 소인수분해

https://www.acmicpc.net/problem/11653

11653번: 소인수분해

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int N, x, i = 2;
	scanf("%d", &N);
	x = N;
		while(x != 1){
			if (x % i != 0) {
				i++;
				continue;
			}
			if (x % i == 0) {
				printf("%d\n", i);
				x /= i;
				i = 2;
			}
	}
		return 0;
}

문제에서 요구한 사항은

1. 주어진 정수 N을 소인수분해하여 소인수를 오름차순으로 한 줄 씩 출력하기

2. N이 1일 경우 아무것도 출력하지 않기

 

소인수분해란 말 그대로 어떠한 자연수를 소인수로 분해하는 것이다. 인수분해의 한 종류다.

소인수란 소수인 인수를 의미하는데 인수란 곱으로 나타나는 수를 의미한다.

따라서 우리는 정수 N을 소수의 곱셈으로 분해해야한다!

 

소인수분해의 공식은 따로 없다. 나눠보아야 한다.

그렇다면 나누는 과정에서 어떻게 더 간결하게 표현할지

디테일적인 조건들을 어떻게 간결하게 표현할지가 핵심이었다.

 

오름차순으로 출력하는 것은 따로 어렵지 않았다.

정수 N이 정수 i와 나눠서 나머지가 0이라면 정수 i는 반드시 소수일 것이다.

따라서 자연스럽게 오름차순으로 표현될 것이다.

i가 합성수라면 반드시 합성수를 구성하는 소수에 이미 걸리기 때문이다.

 

만약 소인수 1개를 찾았다면 정수 N은 소인수로 나눠주고 다시 2부터 판별해야한다.

위를 표현하는 과정에서 2. N이 1일 경우 아무것도 출력하지 않기를 7~8줄에 표현했다.

 

다만 시간이 28ms나 걸렸다.

9번째 줄의 조건문 때문에 while문이 불필요하게 반복되기 때문인걸까

 

#include <stdio.h>

int main(void)
{
    int n, f = 2;
    scanf("%d", &n);
    while (f*f <= n)
    {
        while (n % f == 0 && (n = n / f)) printf("%d\n", f);
        f += f % 2 ? 2 : 1;
    }
    if (n>1) printf("%d\n", n);
}

백준의 정답자 코드를 살펴보던 중 공부할만한 코드라고 생각했다.

우선 첫 while문의 조건문 이는 에라토스테네스의 체의 원리를 이용한 것인데 어떤 수 n이 p와 q의 곱으로 나타난다면 p와 q는 각각 루트n 이상,이하이다.

이것을 이용하여 굳이 루트 N을 초과하여 소인수를 찾을 필요가 없었다.

 

두번째로는

c언어의 유일한 삼항 연산자인 조건 연산자 ?

피연산자로 조건식이 필요하며 그 조건의 결과로 피연산자인 두 개 항에서 하나를 선택한다.

조건식 ? A : B
조건식이 참이면 A를 선택하지만 거짓이면 B를 선택한다.

위 코드에 대입하여 보자

f가 2의 배수이면 거짓이 되어 1을 더하고 -> 홀수로 만들어주고

f가 2의 배수가 아니라면 참이 되어 2를 더해준다 -> 역시 홀수가 유지가 된다.

이유는 소수는 절대 짝수가 될 수 없기 때문이다.

이것을 이용하여 짝수는 2를 제외하고 판별에 관여할 수 없게된다.