소인수분해 알고리즘

본 내용은 youtube 주니온TV 아무거나연구소 의 내용을 전사한 내용입니다.
문제가 될 경우 삭제하도록 하겠습니다.
https://www.youtube.com/watch?v=ZMbw_KGhLD0&list=PLHqxB9kMLLaPOXKVOMqKDk3SSAQx7E-sX&index=8

첫 번째 소인수분해 알고리즘

루트 N 내의 범위에 해당한 모든 약수를 찾아 나눕니다.

import math, random
def addFactor(num_dict, num):
    if num in num_dict:
        num_dict[num] += 1
    else:
        num_dict[num] = 1

def factorize1(n):
    factors = dict()
    sqrtn = math.floor(math.sqrt(n))
    for i in range(2, sqrtn + 1):
        # i가 약수이면  
        while (n% i == 0):
            # dict에 추가
            addFactor(factors, i)
            # 나눈 몫 갱신
            n //= i
    if n > 1:
        addFactor(factors, n)
    return factors

1. (성능개선 1)

소인수는 소수니까, 1 부터 루트 N 까지의 모든 소수만 찾으면?

def isPrime(n):
    sqrtn = math.floor(math.sqrt(n))
    for i in range(2, sqrtn + 1):
        if n % i == 0:
            return False
    return True

def findPrimes(n):
    primes = []
    for i in range(2, n + 1):
        if isPrime(i):
            primes.append(i)
    return primes

소수 판별 알고리즘의 시간 복잡도 분석
단위 연산 : 약수의 판단을 위한 모듈러 연산

• n % i == 0
  입력 크기
• 모듈러 연산 == 나눗셈 연산 == 뺄셈 연산 == 2의 보수 덧셈 연산 == 덧셈연산 == 비트 연산
  알고리즘 단위의 연산에 영향을 미치는 입력 크기는 N의 비트수 만큼이 된다.
  그러면 N의 비트 수는 log2N + 1
  => n = 2^b
  => 지수승 만큼 연산이 늘어납니다
  해당 시간복잡도는 어차피 지수만큼 늘어나게 됩니다.

3. (성능개선 2)

에라토스테네스의 체

def sieve(n):
    # 0,1 을 제외한 모든 정수를 소수로 가정하고 테이블 만듬
    flags = [0, 0] + [1] * (n - 1)
    sqrtn = math.floor(math.sqrt(n))
    # 2부터 루트 n까지
    for i in range(2, sqrtn + 1):
        if flags[i] == 1:
            # i에 해당하는 모든 정수에 대해 i + i는 i의 약수 이므로 2 * i 부터 순회
            #for j in range(2 * i, n + 1, i):
            # 근데 얘는 어차피 2i, 3i, 4i .... 2, 3, 4의 배수 이므로 i * i 부터 안걸러짐
            for j in range(i * i, n + 1, i):
                flags[j] = 0
    primes = []
    for i in range(len(flags)):
        if flags[i] == 1:
            primes.append(i)
    return primes

문제점 : 매우 큰 정수를 담게되면 메모리 이슈가 있습니다

4. (성능개선 3)

세그먼트 에라토스테네스의 체

n이 충분히 크면, n을 루트 n개의 세그먼트로 분할합니다.
첫번째 세그먼트에서 소수를 모두 찾은 뒤, 이 소수들로 다음 세그먼트들을 차례로 방문하여 처리합니다.

def segmented(n):
    sqrtn = math.floor(math.sqrt(n))
    seeds = sieve(sqrtn)
    primes = []
    low = sqrtn
    high = 2* sqrtn - 1
    while low <= n:
        # 세그먼트로 나누었을 때 마지막 세그먼트의 high 값이 n보다 작은경우 n까지 포함시켜줘야 하므로
        if high > n:
            high = n
        flags = [1] * sqrtn
        for i in range(len(seeds)):
            start = (low // seeds[i]) * seeds[i]
            # 만일 start 값이 최초 low 값보다 작을 경우 i만큼 더해주어야 함
            if start< low:
                start += seeds[i]
            for j in range(start, high + 1, seeds[i]):
                flags[j - low] = 0
        # 소수 판별
        for i in range(low, high + 1):
            if flags[i - low] == 1:
                primes.append(i)
        low += sqrtn
        high += sqrtn
    return seeds + primes
# 해당 알고리즘의 시간 복잡도는 O(nloglogn) -> 거의 선형시간이라고 합니다.

두번째 소인수 분해 알고리즘

만약 어떤 N에 대하여 가장 작은 소인수(mpf)를 안다면, N을 mpf로 나눕니다.
만약 N이 mpf 와 같다면 소수입니다.

# N이 1이 되면 종료
def getMPF(n, mpf):
    if n in mpf:
        return mpf[n]
    else:
        sqrtn = math.floor(math.sqrt(n))
        for i in range(2, sqrtn + 1):
            if n % i == 0:
                mpf[n] = i
                return i
        # 소수임
        mpf[n] = n
        return n

def factor2(n):
    mpf = {}
    factors = {}
    while n > 1:
        mpfn = getMPF(n, mpf)
        addFactor(factors, mpfn)
        n = n//mpfn
    return factors
# print(factor2(360))

두번째 소인수 분해 알고리즘의 성능개선

특정 범위의 mpf 를 한번만 계산해서 테이블에 담아두고 이 테이블을 이용해서 소인수 분해를 반복한다면?

최소 소인수 테이블 만들기

def sieve2(n):
    mpf = [0, 0] + [i for i in range(2, n + 1)]
    sqrtn = math.floor(math.sqrt(n))
    for i in range(2, sqrtn + 1):
        # 소수라면 
        if mpf[i] == i:
            # 변경
            for j in range(i * i, n + 1, i):
                if mpf[j] == j:
                    mpf[j] = i
    return mpf


def factorize2(n, mpf):
    factors = dict()
    while n > 1:
        addFactor(factors, mpf[n])
        n //= mpf[n]
    return factors

감사합니다.