[BOJ] 11653번

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

11653번: 소인수분해

 

Python3

code 1

if __name__ == '__main__':
    N = int(input())

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

입력받은 N에 대해서 2부터 N의 제곱근까지의 수들로 나누기를 진행했다. 나누는 수는 제곱근보다 클 수 없기 때문에 반복문의 범위를 제곱근까지로 정하였다. 만약 N이 i로 나누어진다면 나눈 수 i를 출력하고 i로 나눌 수 있을 때까지 반복해서 나누었다. 마지막에 남은 수 N이 1보다 크다면 그 수도 출력했다.

하지만 이방법은 채점을 하기까지 너무 오랜시간이 걸렸고 반복문을 두번 쓰는 방식이 비효율적이라고 느껴져서 다른 방법을 고민했다.

 

code 2

if __name__ == '__main__':
    N = int(input())
    i = 2
    while N > 1:
        if N % i == 0:
            print(i)
            N //= i
        else:
            i += 1

 

다음의 방식으로도 해결할 수 있었다. 이 방식의 경우 N이 1보다 클 때 동안 소수 2부터 시작하는 i로 N이 나누어질 때 i를 출력하고 소인수가 아니라면 i를 증가시키는 방식이다. 첫번째 방식에서 반복문을 하나로 줄였다.

 

Result

첫번째 제출이 상단의 코드고 두번째 제출이 하단의 코드다. 결과는 내 예상과는 달리 상단의 코드가 훨씬 빨랐다. 내 생각으로는 code1은 초반에 소인수가 다 찾아질 경우에도 제곱근까지 반복문을 실행해야하기 때문에 소인수가 다 찾아지면 끝나는 code 2보다 느릴 것이라고 생각했다. 아직까지 이유는 정확하게 모르겠어서 조금 더 찾아봐야겠다.