📍문제

[BOJ] 11653번: 소인수분해

📍풀이

소인수분해란?
1보다 큰 자연수를 소인수(소수인 인수)들만의 곱으로 나타내는 것 또는 합성수를 소수의 곱으로 나타내는 방법
쉽게 말하자면 짝수면 2로 나누고, 홀수면 대충 나눠질 거 같은거로 나눠가면서 소인수들만의 곱으로 나타내는 것을 말한다. (보통 수학할 때 이렇게 했자나요?)

주어진 문제는 자연수가 주어지면 그 자연수에 해당하는 소인수들을 다 풀어서 출력하는 것이다.

📚소인수분해 알고리즘에 대한 고찰

처음에 내가 생각한 방법은
1. 주어진 자연수의 소수 중 가장 작은 수를 구한다. (소수 판별 알고리즘 이용)
2. 이후 주어진 자연수를 그 소수로 나눠가면서 해당하는 숫자를 리스트에 담는다.
3. 리스트를 순서대로 출력
인데.. 사실 이렇게 복잡하게 생각할 필요가 없는 문제였다.
코딩을 시작하고 느낀 나의 고질적인 문제점.. 너무 어렵게 생각한다🤦‍♀️

💻이에 해당하는 코드(오답)

import math
N = int(input())
ans = []
def isPrime(n):
    if n == 1:
        return False
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

for i in range(2, N):
    if isPrime(i) == True:
        sosu = i
        break

while N != 1:
    ans.append(sosu)
    N = N // sosu

ans.sort
for an in ans:
    print(an)

N이 짝수면 2만 출력되고 그외에도 제일 작은 소수만 출력되는 요상한 코드를 짰다ㅋㅋㅋㅋㅋㅋㅋㅋ 근데 이렇게 할 필요가 없었던 코드..
심지어 소수판별 알고리즘 효율 좋은거(에라토스테네스의 체) 배워두고 저런 함수 씀

💻정답 코드

결국 구글링 찬스 씀 👍

N = int(input())
m = 2
while N != 1:  # N과 m을 나눴을 때 몫이 1이 되면 멈춤.
  if N % m == 0: 
    print(m) 
    N = N // m
  else:
    m += 1

어차피 소인수들의 모임을 구하는 거니까 m = 2로 시작하고 N을 m으로 나눴을 때 나누어 떨어진다면, 이를 출력한다.
출력 예시인 72를 예로 들자면 72는 2로 나누어 떨어지니까 2를 출력하고, 이후 N에 N을 m으로 나눈 몫을 다시 저장해준다. (72를 2로 나눈 몫인 36을 저장)
그러면 이제 N은 36이 된다. 36역시 2로 나누어 떨어지니까 2를 출력하고 이후에 36을 2로 나눈 몫인 18을 저장한다.
계속 진행하다 보면 18을 2로 나누면 몫이 9가 되고, 9는 2로 나누어떨어지지 않으니 m에 1을 더해주고 반복문을 다시 돈다.
9는 3으로 나누어 떨어지고, 몫이 3이된다. 이후 또 3으로 나누면 몫이 1이 되므로 반복문 탈출.

소인수분해를 정확히 언제 배웠는지 기억은 잘 나지 않지만 우리가 손으로 쓰면서 소인수분해를 진행하는 과정을 완벽하게 담은 코드라고 생각이 든다.