for textmining

소인수분해

07 Oct 2017 | algorithm

이번 글에서는 소인수분해 알고리즘에 살펴보도록 하겠습니다. 파이썬 코드는 이곳과 이곳을 참고하였습니다. 그럼 시작하겠습니다.

소수 찾기

소수란 1과 자기 자신만을 약수로 갖는 수를 가리킵니다. 어떤 숫자 num이 소수인지 아닌지 판별하는 가장 간단한 방법은 num까지의 모든 숫자를 나누어보는 것입니다. 다음과 같습니다.

def check_prime(num):
    # prime numbers are greater than 1
    if num > 1:
        # check for factors
        for i in range(2, num):
            if (num % i) == 0:
                print(num, "is not a prime number")
                print(i, "times", num // i, "is", num)
                break
        else:
            print(num, "is a prime number")

    # if input number is less than
    # or equal to 1, it is not prime
    else:
        print(num, "is not a prime number")

특정 범위 내 소수들 찾기

소수를 발견하면 그 소수의 배수인 모든 수들을 소수 리스트에서 지웁니다. 범위 내 숫자들 중 소수가 아닌 것들을 거르는 과정을 반복하다보면 결국 소수만 남게 됩니다. 이를 에라토스테네스의 체(Sieve of Eratosthenes)라고 합니다. 다음과 같습니다.

import math
def primeSieve(sieveSize):
    # creating Sieve (0~n까지의 slot)
    sieve = [True] * (sieveSize+1)
    # 0과 1은 소수가 아니므로 제외
    sieve[0] = False
    sieve[1] = False
    # 2부터 (루트 n) + 1까지의 숫자를 탐색
    for i in range(2,int(math.sqrt(sieveSize))+1):
        # i가 소수가 아니면 pass
        if sieve[i] == False:
            continue
        # i가 소수라면 i*i~n까지 숫자 가운데 i의 배수를
        # 소수에서 제외
        for pointer in range(i**2, sieveSize+1, i):
            sieve[pointer] = False
    primes = []
    # sieve 리스트에서 True인 것이 소수이므로
    # True인 값의 인덱스를 결과로 저장
    for i in range(sieveSize+1):
        if sieve[i] == True:
            primes.append(i)
    return primes

위 알고리즘에서 소수 탐색 범위가 $\sqrt{n}$까지인 이유는 약수가 존재하는 숫자의 반이 이 범위에 존재하기 때문에 이 범위를 탐색하는 것만으로도 전체 범위에서 약수의 존재 여부를 확신할 수 있습니다.

소인수분해

에라토스테네스의 체 알고리즘을 활용해 소인수분해를 하는 알고리즘은 다음과 같습니다.

# 소인수분해
def get_prime_factors(n):
    # n 범위 내의 소수를 구한다
    primelist = primeSieve(n)
    # 이 소수들 중 n으로 나누어 떨어지는
    # 소수를 구하고, 몇 번 나눌 수 있는지 계산
    # 예 : n = 8, factors = [(2, 3)]
    # 예 : n = 100, fcount = [(2: 2), (5: 2)]
    factors = []
    for p in primelist:
        count = 0
        while n % p == 0:
            n /= p
            count += 1
        if count > 0:
            factors.append((p, count))
    return factors



Related Posts

Comments