[BOJ 11653] 소인수분해

1) 문제 링크

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

2) 접근

처음에는 소수 table을 만들어야 하나… 까지 생각했지만 소인수분해에서는 필요없음을 깨달았다. 어떤 자연수 N이 소수 a의 배수의 배수이면 a의 배수이며 a를 제외한 a의 배수는 a보다 크기가 반드시 크기 때문에, for문으로 작은 수부터 돌리면 소수 여부는 판단할 필요가 없기 때문이다. 그래서 N이 1이 될 때까지 가장 작은 약수를 찾으며 계속 나누는 방식으로 코드를 짰다.

3) 풀이

처음 짠 코드는 이렇다.(Python)

a = int(input())
while a > 1:
    for i in range(2, a+1):
        if a%i == 0:
            print(i)
            a //= i
            break

1068ms… 너무 오래 걸린다. 시간복잡도는 $O(m\sqrt{n})$쯤 되려나.

4) 피드백

다른 분들의 코드를 참고하던 중 약간 발상만 바꿔도 시간복잡도가 확 줄어들 수 있음을 깨닫고 다시 짰다.(Python)

a = int(input())
for i in range(2, int(a ** 0.5)+1):
    while(a%i == 0):
        a //= i
        print(i)
if(a>1):
    print(a)

솔직히 시간복잡도 표기법 상으로 무슨 차이가 있는지는 모르겠지만 직관적으로 봤을 때 수행시간이 줄어드는 건 확실하다. 순서만 잘 바꿔도 시간이 확 줄어듦을 배운 문제였다.

+(2021-08-12) 에라토스테네스의 체에 대해 kks227님의 블로그를 토대로 공부한 뒤 이 문제에 대해 보다 많은 생각을 할 수 있었고, 시간복잡도에 대해서도 새로운 사실 몇 가지를 알 수 있었다. 이에 대해 향후 수정을 통해 구체적으로 설명할 것이다.