정수 N이 주어졌을 때, N를 소인수분해하는 문제.

접근

N이 주어졌을 때, 2로 나누다가, 3으로 나누다가, ... 이렇게 쭉 올라가면 되지 않을까? 얼마나 나눠야할지는 어떻게 알 수 있을까? 한번 전수조사해보자!

내 첫번째 코드이다.

from math import prod

n = m = int(input())

ls = [1]
i = 2
while prod(ls) != m:
    if n % i == 0:
        ls.append(i)
        n //= i
    else:
        i += 1
    
ls.remove(1)
print(*ls)

math 라이브러리의 prod 함수를 사용해 만약 N이 어떤 수 i로 나눠진다면, ls에 넣고, 리스트 내의 모든 값의 곱이 N과 같아지기 전까지 반복한다. 그리고 리스트에서 1을 제거한 뒤 리스트의 값들을 출력한다.

생각해보니 prod까지 갈 필요도 없었다. 게다가 2384ms나 걸리는 엄청 느린 코드이다. 좀 더 개선해보자.

n = m = int(input())

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

prod함수를 사용하는 대신 n이 i로 나누어떨어지지 않을 때까지 x에 i를 곱해나갔다. 불필요한 리스트 연산을 제거함으로 더 빠른 코드(1548ms)를 짤 수 있었다. 하지만 아직 뭔가 느리다. 왜 느리지?
어떻게 더 효율적인 코드를 짤 수 있을까? i에 1씩 더하는 대신 다음 소수로 바로 넘어갈 수 있으면 좋을텐데. ... 소수라고?

백준 2581. 소수

전에 풀었던 백준 2581번 소수 문제에서 다른 코드를 살펴본 적이 있었다. 그때도 내 코드가 느린 감이 있었는데, 아니나다를까 수의 성질을 사용한 트릭을 사용하고 있었다. 바로 이해할 수는 없었다.

m = int(input())
n = int(input())
l = [1] * (n + 1)   # 1이 n + 1개 담긴 하나의 리스트
l[1] = 0
for i in range(2, int(n ** (0.5)) + 1):   # 정수론
    if l[i]:
        for j in range(i * i, n + 1, i):
            l[j] = 0

l=[i for i in range(m, n + 1) if l[i] == 1]
if sum(l) == 0:
    print(-1)
else:    
    print(sum(l))
    print(min(l))

이런 코드였다. for 반복문의 조건에 보면 n ** (0.5)가 보인다. 뭐지? 어떤 성질을 어떻게 사용한거지? 수학을 좀 더 열심히 해둘껄 하는 후회감도 들었다. 하지만 이제 나는 수학 전공자가 아니다. 현실을 받아들이고 해결책을 찾아보기 시작했다.

에라스토테네스의 체

고대 그리스의 수학자 에라스토테네스는 소수를 찾는 방법을 고안했다. 나무위키에서는 임의의 자연수 $N$에 대해 그 이하의 소수를 찾는 가장 빠른 방법이라고 한다. 예를 들어 $N$이 $100$이라 할 때, 먼저 $1$을 거르고, $2$의 배수를 거르고, 다음은 $3$의 배수, $4$의 배수는 이미 걸러졌으므로 $5$의 배수.. 이런식으로 나가다가 $100$의 제곱근인 $10$의 배수까지 다 걸렀으면 다 걸러졌다는 것이다.

[!Caveat]
다만 에라토스테네스의 체는 '특정 범위 내의 소수'를 판정하는 데에만 효율적이다. 만약 주어진 수 하나가 소수인가? 만을 따지는 상황이라면 이는 소수판정법이라 해서 에라토스테네스의 체 따위와는 비교도 안되게 빠른방법이 넘쳐난다. (출처: 나무위키)

증명

왜 그럴까? 한 글을 참고하여 증명을 적어보기로 한다.

먼저 어떤 합성수 $N = A * B$라 하자 (단 $A \geq B$).
이 때, $N$을 $B$로 나누었을 때, 나누어 떨어지므로, $A$ 또한 $N$의 인수가 됨을 알 수 있다. 그리고 $\sqrt{N} \leq A$ 이므로 $\sqrt{N}$까지 확인하면 $N$의 모든 소인수들을 확인할 수 있다.

다시 돌아와서, 세 개의 코드

그렇다면 i를 N까지 증가시키지 않고도, N ** .5까지만 확인하고도 코드를 끝낼 수 있다는 말이 된다. 이 수학적 사실을 적용해보자. 세 군데 코드를 추가하여 성능을 시험해봤다.

메모리 약 30MB, 시간 36ms

n = m = int(input())

x = 1
i = 2
while x != m:
    if n % i == 0:
        x *= i
        n //= i
        print(i)
        
    elif i > n ** .5:
        if n != 1:
            print(n)
        break

    else:
        i += 1

속도가 확실히 빨라졌다.

메모리 약 30MB, 시간 44ms

n = m = int(input())

x = 1
i = 2
while x != m:
    if i > n ** .5:
        if n != 1:
            print(n)
        break
    
    if n % i == 0:
        x *= i
        n //= i
        print(i)

    else:
        i += 1

메모리 약 30MB, 시간 36ms

n = m = int(input())

x = 1
i = 2
while x != m:
    if n % i == 0:
        x *= i
        n //= i
        print(i)

    else:
        i += 1
        if i > n ** .5:
            if n != 1:
                print(n)
            break
    

세 코드 다 메모리는 비슷하지만, 시간에서 약간 차이가 난다. 어디에 아까 배운 수학적 지식을 삽입하는게 좋을까? (모든 코드에서 i가 n ** .5보다 커지면 반복문을 종료하는 코드를 확인 할 수 있을 것이다.)

첫번째 코드와 두번째 코드는 비슷한 것 같지만, 두번째 코드에서 조건을 두번 체크해야 하기 때문에 약간 늦어진 것으로 추측할 수 있다. 세번째 코드는 i에 1을 더할 때마다 i를 확인한다. 첫번째 코드 또한 나누어 떨어지지 않을 때마다 i가 n의 제곱근보다 큰지 확인하기 때문에, 세번째 코드와 첫번째 코드는 기능적으로 같다고 볼 수 있다.

결론

정수론적 지식을 코드에 적용함으로 성능을 높일 수 있었다. 에라스토테네스의 방법에 의하면 합성수의 제곱근의 배수를 제거함으로서 그 수 까지의 소수들을 남길 수 있다. 이 지식을 코드에 적용해 i가 n ** .5이하일 경우까지만 확인해, 성능을 약 30배가량 높였다.

마치며

소수 판별하는 빠른 방법들이 있다고 했는데, 궁금해진다.

잘 하고 있다.