[Python] 소인수 분해, 약수 구하기

소인수 분해

소인수 분해를 하기 위해선 이전에 정리한 에라토스테네스의 체 방식을 사용한 소수 구하기를 사용하여 변형하는 것이 좋습니다. (https://brownbears.tistory.com/445)

아래는 특정 값이 주어졌을 때, 소인수 분해를 한 예시입니다.

import math def get_primes(n): # 구하고자 하는 수만큼 True를 갖는 리스트 생성 is_primes = [True] * n # n의 최대 약수가 sqrt(n) 이하이므로 계산한 후, 소숫점이 있을 경우 올림으로 최대 반복 횟수 계산 max_length = math.ceil(math.sqrt(n)) for i in range(2, max_length): # True일 경우, 소수 if is_primes[i]: # i이후 i의 배수들을 지워나감 for j in range(i + i, n, i): is_primes[j] = False # 리스트의 True로 남아 있는 인덱스(소수)를 추출 return [i for i in range(2, n) if is_primes[i]] def get_factorization(num): factors = [] for prime in get_primes(num): count = 0 while num % prime == 0: num /= prime count += 1 if count > 0: factors.append((prime, count)) get_factorization(12) # [(2, 2), (3, 1)]

약수 구하기

소인수 분해를 사용해 구하는 방법, 단순하게 1부터 주어진 수까지 구하는 방법이 있습니다. 소인수 분해를 사용해 구하는 방법은 위의 코드를 사용하기 때문에 단순히 구하는 방법보다 어렵습니다.

아래는 단순하지만 효과적인 방법으로 만든 예제입니다.

import math def get_divisor(num): divisors = [] length = int(math.sqrt(num)) + 1 for i in range(1, length): if num % i == 0: divisors.append(i) divisors.append(num//i) divisors.sort() return divisors print(get_divisor(90)) # [1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90]

에라토스체네스의 체와 같이 주어진 수만큼 반복문을 진행할 필요없이 10^2 > 90 이므로 11보다 작은 수만큼 나누면 결과를 얻을 수 있습니다.

약수 개수 구하기

약수의 개수는 소인수 분해와 위의 약수 구한 예제 코드로 구할 수 있습니다.

두 코드의 수행속도를 비교한 예제 입니다.

import math import timeit ## 약수 개수 구한 코드 def get_divisor(num): divisors = [] length = int(math.sqrt(num)) + 1 for i in range(1, length): if num % i == 0: divisors.append(i) divisors.append(num//i) divisors.sort() return divisors ## 소인수 분해를 위한 코드 def get_primes(n): # 구하고자 하는 수만큼 True를 갖는 리스트 생성 is_primes = [True] * n # n의 최대 약수가 sqrt(n) 이하이므로 계산한 후, 소숫점이 있을 경우 올림으로 최대 반복 횟수 계산 max_length = math.ceil(math.sqrt(n)) for i in range(2, max_length): # True일 경우, 소수 if is_primes[i]: # i이후 i의 배수들을 지워나감 for j in range(i + i, n, i): is_primes[j] = False # 리스트의 True로 남아 있는 인덱스(소수)를 추출 return [i for i in range(2, n) if is_primes[i]] def get_factorization(num): factors = [] for prime in get_primes(num): count = 0 while num % prime == 0: num /= prime count += 1 if count > 0: factors.append((prime, count)) return factors def get_divisor_cnt(num): divisor_length = 1 for factor in get_factorization(num): divisor_length *= factor[1] + 1 return divisor_length # 12의 약수 개수 실행속도 t1 = timeit.timeit('len(get_divisor(12))', setup="from __main__ import get_divisor", number=1) t2 = timeit.timeit('get_divisor_cnt(12)', setup="from __main__ import get_divisor_cnt", number=1) # 2.378108911216259e-05 # 7.567903958261013e-05 # 1000000의 약수 개수 실행속도 t1 = timeit.timeit('len(get_divisor(1000000))', setup="from __main__ import get_divisor", number=1) t2 = timeit.timeit('get_divisor_cnt(1000000)', setup="from __main__ import get_divisor_cnt", number=1) # 0.00011199899017810822 # 0.267205539974384

약수 개수를 구하는 속도는 소인수 분해를 통해 구하는 것보다 단순하게 약수를 구하는 것이 훨씬 빠른 것으로 확인이 됩니다.

요약

소인수 분해를 구하는 것이 아닌, 약수를 구하는 문제라면 굳이 소인수 분해를 할 필요가 없다.