소인수분해로직

소인수분해1하기에 관한 알고리듬. 예전에는 클래스를 하나 만들어서 n보다 작은 소수의 리스트를 먼저 구해서 이를 사용했지만, 아래 알고리듬이 훨씬 빠르기 때문에 오일러프로젝트 문제 풀이에 매우 유용하다. 특히 나눌 수 있는 최소의 숫자를 찾는 함수에서 2, 3, 5로 먼저 나눠본 후 7에서 시작해서 4, 2를 번갈아 가면서 더하는 로직을 눈여겨보자. 이를 통해 3의 배수로 나눠보는 케이스를 최소화할 수 있다.

def factor(n):
    """
    주어진 수를 소인수 분해한다. 

    >>> factor(786456)
    [(2,3), (3,3), (11,1), (331,1)]
    """

    #### 2보다 큰 양수에 대해서만 유효하다.
    if n in [-1, 0, 1]: return []
    if n < 0: n = -n

    F = []
    while n != 1:
        p = trial_division(n) # n을 나눌 수 있는 최소의 소수를 찾는다.
        e = 1
        n /= p
        while n%p == 0:
            e += 1; n /= p
            # p로 나눌 수 있을 때까지 n을 계속 나눈다.
            # 시행횟수를 센다.
        F.append((p,e))
    F.sort()
    return F


def trial_division(n, bound=None):
    if n == 1: return 1
    for p in [2, 3, 5]:
        if n%p == 0: return p
    if bound == None: bound = n
    dif = [4, 2]
    ### !!! 7 > +4 > +2 > +4 > ..  
    ### !!! 이런 식으로 더해가면 초반에 소수랑 많이 만날 수 있게 된다. 3의 배수를 이런 식으로 미리 피하여 가능한한 계산 횟수를 줄인다.
    m = 7; i = 1
    while m <= bound and m*m <= n:
        if n%m == 0:
            # 만약 m이 소수가 아니라면 n은 m의 약수 중 하나로 벌써 나눠졌을 것이다.
            return m 
        m += dif[i%2] # 7 > 11, 13, 17, 19, 23, 29, 31, 37... 
        i += 1
    return n

  1. 모든 소인수와 각 소인수의 개수(지수)를 모두 구하는 것.