알고리즘 - Python / 백준 - 4149번 : 큰 수 소인수분해

4149번: 큰 수 소인수분해 (acmicpc.net)

4149번: 큰 수 소인수분해

 

---

풀이

• 1 ~ 2^62 사이의 수를 소인수 분해하고 모든 인수를 오름차순으로 출력하는 문제다.
• 범위가 매우 넓기 때문에 일반적인 소인수 분해로는 해결할 수 없다.
• 따라서 O(n^(1/2)) 시간 복잡도의 일반적인 소인수 분해 알고리즘이 아닌 O(n^(1/4)) 시간 복잡도를 가지는 폴라드 로 알고리즘을 사용해서 풀어야 한다.
• 물론 폴라드 로 알고리즘도 모든 수에 대하여 O(n^(1/4)) 시간 안에 모든 인수를 구하는 것이 확률 적으로 추측될 뿐 , 엄밀한 수학적 증명은 아직 이루어지지 않았다.
• 폴라드 로 알고리즘의 구현과 개념에 대해서는 아래 위키 문서를 참고하자.

 

 

폴라드 로 알고리즘 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

폴라드 로 알고리즘 - 위키백과, 우리 모두의 백과사전

 

 

• 폴라드 로 알고리즘을 통해 인수를 찾는데 , 포인트는 소인수 분해다.
• 인수를 찾긴 찾아도 그게 소수인지 아닌지 알아야 한다는 것이다.
• 소수인지 아닌지를 효율적으로 검사해야 하므로 밀러-라빈 소수 판별법을 사용해야 한다.
• 밀러-라빈 소수 판별법에 대한 내용은 아래 위키 문서를 참고하자.

 

 

밀러-라빈 소수판별법 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

밀러-라빈 소수판별법 - 위키백과, 우리 모두의 백과사전

 

 

• 폴라드 로 알고리즘으로 인수를 찾고 , 그 인수가 소수인지 아닌지 판별한다.
• 만약 소수라면 정답 리스트에 추가하고 , 아니라면 그 소수가 아닌 수를 다시 소인수 분해한다.
• 이러한 방식을 재귀적으로 구현하였고 , 재귀 끝부분에서는 반드시 소수가 나온다고 생각하였다.
• 이런 식으로 나온 정답 소인수들을 리스트에 추가하고 마지막에 혹시 모를 비 오름차순 때문에 정답 배열을 오름차순으로 sort 한다.
• 밀러-라빈 소수 판별법에서는 검사할 수의 범위에 따라 a가 달라지는데 이 문제의 경우 최대 2^62 까지 요구하고 있다.
• 이 경우 사용할 a는 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 이다.
• 밀러-라빈 소수 판별법을 이용한 또 다른 백준 문제는 5615번 , 아파트 임대 문제가 있다.
• 이번 문제 풀이에서 사용한 밀러-라빈 소수 판별법 코드도 이전에 풀었던 5615번의 코드를 재활용하였다.

 

import sys

def powmod(a,b,m):
    result = 1
    while b > 0:
        if b % 2 != 0:
            result = (result * a) % m
        b //= 2
        a = (a * a) % m

    return result

def mr(n,a):
    r = 0
    d = n-1
    while (d%2 == 0):
        r += 1
        d = d // 2
    x = powmod(a,d,n)
    if x == 1 or x == n-1:
        return True
    for i in range(0,r-1):
        x = powmod(x,2,n)
        if x == n-1:
            return True
    return False

def check_prime(k):
    check = 0
    if k <= 71:
        if k in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]:
            return True
        else:
            return False
    else:
        for i in [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
            if mr(k,i) == False:
                break
            else:
                check += 1
        if check == 12:
            return True
        else:
            return False

n = int(sys.stdin.readline())

def gcd(a, b):
    if b > a:
        k = a
        a = b
        b = k
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

def g(x,n):
    return ((x*x) + 1) % n


def pola(n,x):
    p = x
    if check_prime(n):
        return n
    else:
        for i in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]:
            if n % i == 0:
                return i
        y = x
        d = 1
        while d == 1:
            x = g(x,n)
            y = g(g(y,n),n)
            d = gcd(abs(x-y),n)
        if d == n:
            return pola(n,p+1)
        else:
            if check_prime(d):
                return d
            else:
                return pola(d,2)
ans = []
while n != 1:
    k = pola(n,2)
    ans.append(int(k))
    n = n // k
ans.sort()
for i in ans:
    print(i)

---