[BOJ] 소인수분해 - 11653

문제

 

 

접근 방법

부끄럽지만 일단 소인수 분해에 대해 다시 찾아봤다..

소인수분해란, 어떤 자연수를 소인수(소수인 인수)들의 곱으로 나타내는 것이다.

 

그렇다면 '소수'란 무엇인가?

소수는 1과 자기 자신만을 인수로 갖는 수를 말한다.

 

그렇다면 우리가 구해야 할 것은 '소수'라고 생각해서, 나눠주는 과정 속에서 그 다음 소수로 나눠주고, 안나눠지면 또 다른 소수를 나눠주면 되겠다 생각했다.

while n == i:
    if n % i != 0 :
        n = n // i;
        print(i)
    else:
        i += 1
        if i % 2 == 0:
            i += 1

 

다음과 같이 접근하여, 자연수를 소수를 인수분해 하면 n이 인수가 될 때 까지 반복하면 끝난다는 사실을 알아냈다.

따라서 이를 loop의 종료조건으로 설정하였다.

 

주어진 n을 나눌 소수를 찾기 위해, 2부터 시작하여 +1을 해주었다.

허나 아무리 생각해도 소수를 찾는 조건을 생각하기 어려웠다.

 

정답

n = int(input())
i = 2

while n != 1:
    if n % i == 0:
        print(i)
        n = n // i
    else:
        i += 1

 

솔루션을 참고하였고, 솔루션에서는 소수를 구하지 않고 '나눠지는 가장 작은 수'를 구하면 된다고 하였다.

과정을 이해하기 위해서 지쌤께 여쭤보았다.

여기서 중요한 점은 i가 n으로 나누어 떨어지면(n % i == 0), i가 n의 소인수라는 것입니다.
그리고 i가 2부터 시작하여 1씩 증가한다는 사실이 중요합니다.

소인수란, 어떤 수를 나눌 수 있는 소수를 말합니다. 즉, n이 i로 나누어 떨어진다면(n % i == 0), i는 n의 인수 중 하나입니다.
여기서 추가적으로 i가 소수일 경우, 그것을 n의 소인수라고 합니다.

i가 2부터 시작하여 순차적으로 증가한다는 사실이 왜 중요할까요? 이유는 단순합니다.
모든 합성수는 소수의 곱으로 표현될 수 있기 때문입니다.
즉, 만약 i가 합성수라면, 그것을 구성하는 더 작은 소수들로 n이 이미 나누어져 있을 것입니다.

예를 들어, n이 12이고 i가 4에 도달했다고 가정해 봅시다. 여기서 4는 소수가 아닙니다. 그러나 4가 12를 나눌 수 있다 해도, 그 이전에 2(4의 소인수)가 이미 12를 나누었을 것입니다.
따라서, 우리는 이미 2라는 소인수를 찾았고, 4를 고려할 필요가 없게 됩니다.

이 알고리즘에서는 i를 천천히 증가시키면서 n을 나눌 수 있는지를 검사합니다.

만약 n을 i로 나누어 떨어트릴 수 있다면, i는 n의 소인수입니다. i를 1씩 증가시키는 이유는 가장 작은 소인수부터 찾아 나가기 위함입니다. 만약 i가 소수가 아니면, 그것은 이전 단계에서 이미 다른 소인수에 의해 n이 나누어졌다는 의미이며, i는 고려할 필요가 없습니다.

결론적으로, 이 알고리즘은 i가 2부터 시작하여 순차적으로 증가함으로써, n을 나눌 수 있는 가장 작은 소인수부터 찾아내어 출력하게 됩니다. i가 합성수인 경우에는 그 합성수를 구성하는 더 작은 소수들로 이미 n이 나누어졌기 때문에, 실제로 출력되는 것은 항상 소인수입니다.

 

결국 i가 늘어나면서 소수 또는 합성수 둘 중 하나가 될 터인데 i가 합성수인 경우에는 그 합성수도 소수들로 이뤄지기 때문에 if문을 타지 않고 +1만 하게 되어 다른 소수를 찾게 되는 것이다.

 

후기

예전 1주차에 키워드로 정수론이 있었던 것이 기억난다.

역시 로직에는 그만한 이유가 다 있다는 것을 느낀다.

 

이와 별개로 이전에 소수판별 알고리즘을 공부했던 기억이 있다.

여러 방법이 있는데, 가장 기억에 남는 것은 '에라토스테네스의 체'이다.

 

쉽게 말하자면, 소수가 맞는지 판별하기 위해 나눠주는 수를 하나 하나 판별하는 과정을 줄이는 알고리즘이다.

수도코드는 다음과 같다.

1. 2 ~ N까지의 범위가 담긴 배열을 만든다.
2. 해당 배열 내의 가장 작은 수 i 부터 시작하여, i의 배수들을 해당 배열에서 지워준다. (i는 소수이기 때문에 i자체는 지우지 않는다.)
3. 주어진 범위 내에서 i의 배수가 모두 지워지면 i 다음으로 작은 수의 배수를 같은 방식으로 배열에서 지워준다.
4. 더 이상 반복할 수 없을 때까지 2, 3번의 과정을 반복해준다.

 

관련된 좋은 글이 있어서 공유해보겠다.

https://seongonion.tistory.com/43

소수판별 알고리즘 - 파이썬 (Python)