BOJ 4149 - 큰 수 소인수분해 (Python3)
아마 모두의 첫 다이아몬드 티어가 아닐까.
소수 판정법과 소인수분해에 관해서는 거의 마법이나 다름없는 두 가지 알고리즘을 잘 쓰면 된다.
밀러-라빈 소수판정법과 폴라드-로 소인수분해 알고리즘. 작동 방식만 알고 있으면 그리 어렵지 않게 풀 수 있다.
그 작동 방식을 이해하는 것이 최소 다이아몬드라는 것은 잊어 두자.
그럼 본격적으로 풀이에 돌입해 보자.
문제
큰 수를 소인수분해 해보자.
입력
입력은 한 줄로 이루어져 있고, 소인수분해 해야 하는 수가 주어진다. 이 수는 1보다 크고, \(2^{62}\)보다 작다.
예제 입력)
18991325453139
출력
입력으로 주어진 양의 정수를 소인수분해 한 뒤, 모든 인수를 한 줄에 하나씩 증가하는 순서로 출력한다.
예제 출력)
3
3
13
179
271
1381
2423
내 코드
from random import randrange
from sys import setrecursionlimit
pli = [2,3,5,7,11,13,17,19,23,29,31,37,41,43]
setrecursionlimit(10**6)
# Miller-Rabin Test
def power(x,y,p):
if y<2: return (x**y)%p
else:
d = y//2
if y%2 == 0: return (power(x,d,p)**2)%p
else: return (x*(power(x,d,p))**2)%p
def miller_rabin(n,a):
r,d = 0,n-1
while d%2 == 0: r += 1; d //= 2
x = power(a,d,n)
if x == 1 or x+1 == n: return True
for i in range(0, r-1):
x = power(x,2,n)
if x+1 == n: return True
return False
def isprime(n):
if n in pli: return True
if n == 1 or n%2 == 0: return False
for p in pli:
if not miller_rabin(n,p): return False
return True
# Pollad-Rho algorithm
def gcd(a,b):
if a<b: a,b = b,a
while b != 0: a,b = b,a%b
return a
def rho(n):
if isprime(n): return n
if n == 1: return 1
if n%2 == 0: return 2
x,c,d = randrange(2,n),randrange(1,n),1
y = x
while d == 1:
x = ((x**2%n)+c)%n
y = ((y**2%n)+c)%n
y = ((y**2%n)+c)%n
d = gcd(n,abs(x-y))
if d == n: return rho(n)
if isprime(d): return d
else: return rho(d)
# Answer Code
n = int(input())
li = []
while n != 1:
d = rho(n)
li.append(d)
n //= d
li.sort()
for i in li: print(i)
역시 다이아몬드. 코드가 길고 길어서 끝이 없다.
첫 번째와 두 번째, 밀러-라빈과 폴라드-로에 관한 해설은 해당 포스트에 자세하게 적혀 있으니 그 포스트를 참조 바란다.
큰 수의 소인수분해 시 재귀가 끝없이 벌어질 수 있으니 미리 재귀 한도를 setrecursionlimit를 이용하여 1백만 번으로 높여 두자.
그게 없어도 통과가 될 수 있으나, 되지 않을 확률도 0은 아니기 때문에 미리 세팅하여 두는 것이 낫다. 안 해 두어 나쁠 것도 없다.
Answer Code에서, li는 소인수를 저장하는 배열이 될 것이다.
rho(n)은 n의 임의의 소인수를 뱉는 코드이기 때문에, 순서대로 정렬된다는 보장이 전혀 없다.
따라서 모든 공정이 마쳐진 후 리스트의 정렬은 필수불가결하다. 그렇지 않는다면 맞게 짰는데 왜 틀렸는지 되뇌이게 될 것이다.
이로서 4149번의 풀이를 마친다.
