소인수분해
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
이번 글에서는 소인수분해 알고리즘에 살펴보도록 하겠습니다. 파이썬 코드는 이곳과 이곳을 참고하였습니다. 그럼 시작하겠습니다.
소수 찾기
소수란 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
