백준 11653번 (F)

백준 온라인 저지 11653번 소인수분해

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

---

제한 조건

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

---

처음 내 상태

• 이미 배운 소수 판별 함수를 장착하고 있던 나였던지라, 아주 기세가 등등했다.
• 앞의 두 문제는 거의 프리패스해서 더 그랬던 것 같다.
• 이거 왜못품? 하고 바로 달려들었다.

from math import sqrt

def isPrime(n):
    if n < 2:
        return False
    elif n == 2:
        return True
    
    for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
            return False
    
    return True

n = int(input())
numbers = [x for x in range(n+1) if isPrime(x)]

index = 0
while index < len(numbers):
    selected = numbers[index]
    if selected > n:
        break

    if n % selected == 0:
        n /= selected
        print(selected)
    else:
        index += 1

• 예상이 산산이 부서지는 데에는 오래 걸리지 않았다. "시간 초과"

---

시간 초과, 또 시간 초과

• 분명 작은 소수 순서대로 계속 나누는 걸텐데. 이해가 안 됐다.
• 2로 계속 나누고, 더 이상 안 나눠지면 3으로 계속 나누고, 반복하는 거 맞지 않나??
• 그래서 기껏 나눠줄 소수 목록까지 뽑아 놨는데 시간초과라니.
• 이후 방법론을 비슷하게 가져가면서 계속 제출했지만 계속 시간초과. 슬슬 화가 나기 시작했다.

---

실버5는 이유가 있다

• 결국 블로그를 참고했다.
• 오잉? 소수인지 판별도 안 하고 그냥 나눠버리네?
• 이 때 인식했다. 2로 더이상 나눠지지 않으면 4로도 나눠지지 않겠구나.
• 즉, 자연수들로 그냥 쭉쭉쭉 나눠주면 뒤에 나오는 해당 소수들의 배수는 그냥 건너뛰겠구나.
• 내가 작성한 소수 판별 함수가 시간을 오히려 더 잡아먹게 했구나... 하는 것.

n = int(input())
for number in range(2, n+1):
    if number > n:
        break

    while n % number == 0:
        n /= number
        print(number)

• 정답 처리된 코드는 정말 허무할 정도로 간단했다.
• 이것도 1.5초인가 걸렸다. 백준의 빡빡한 시간제한을 마구 욕하고 싶었따.