(정수론/파이썬) 소인수분해 구하기

'친절한 수론 길라잡이' 83페이지 연습문제 11.4

 

11.4 오일러 함수의 함수값인 phi(n)을 계산하는 프로그램을 만들어라. 1과 n사이의 모든 수들에 대해 n과 서로소인 수 a를 찾는 방법 말고, n의 소인수분해를 이용하는 방법을 사용해 phi(n)을 계산하라.

 

# 소수 판정 함수. 소수면 True, 아니면 False 반환
def isPrime(num):
  root_val = round(num ** 0.5) # 제곱근 값을 구한다
  for i in range(2, root_val+1): # 제곱근값+1 까지만 약수를 조사해도 충분하다
    if num % i == 0:  # 중간에 나눠지면 소수가 아니다
      return False
  return True

# 약수 구하는 함수
def getDivisor(num):
  divisors = []
  root_num = round(num ** 0.5)
  
  for i in range(1, root_num+1):
    if num % i == 0:
      divisors.append(i)
      divisors.append(num // i)
  return sorted(list(set(divisors)))


# 인수분해를 해서 결과를 딕셔너리로 반환
# 가령 인수분해 결과가 2^3 * 3^2 * 7 이라면
# {2:3, 3:2, 7:1} 반환
def factorize(num):
  divisor_primes = [] # 분해된 인수를 차곡차곡 저장하는 리스트
  factorize_dict = {} # 리스트의 원소 갯수를 세어 넣는 용도
  
  # num이 소수라면 (num, 1)을 딕셔너리에 넣어 반환한다.
  # 소수 판정은 숫자의 제곱근까지만 조사하면 되므로 간단하다.
  if isPrime(num):
      factorize_dict[num] = 1
      return factorize_dict
  
  # 인수분해 루틴은 소수 판정 루틴과는 조금 다르게 접근할 필요가 있다.
  i = 2
  while True:
      # i가 소수인지 검사해서 소수라면 num을 i로 나눈다
      # i로 나눠서 나머지가 0이라면, 인수분해가 한번 된 것이다.
      if isPrime(i) and num % i == 0:
          divisor_primes.append(i) # 나누는 수를 저장 (가령, num이 12라면 i = 2)
          num = num // i   # 몫, 가령 24//2 = 12
          #print(f"{i}, {num}")
          # 12는 소수가 아니므로 반복문 계속. 소수가 나오면 그 소수를 저장하고 반복문 종료.
          if isPrime(num):
              divisor_primes.append(num)
              break  # return divisor_primes
          i = 2 # 인수분해를 한번 했으므로 숫자를 2로 다시 나눠보기로 설정
      else:
          i += 1 # 인수분해가 되지 않으면 젯수(나누는 수)를 1증가
  print(divisor_primes)
  
  for n in divisor_primes:
      if n in factorize_dict:
          factorize_dict[n] += 1   
      else:  
          factorize_dict[n] = 1      

  return factorize_dict


print(factorize(24))
print(factorize(1512)) # 2^3* 3^3 * 7
print(factorize(3600)) # 2^4* 3^2 * 5^2
print(factorize(2147483647)) # 소수

num = 3600
result = factorize(num) # 2^4* 3^2 * 5^2
length = len(result) 
print (f"{num} = ", end="")
for i, (k, v) in enumerate(result.items()):
    print(f"{k}^{v}", end="")
    if i == length - 1: break # 마지막 항목에는 * 표시를 덧붙이지 않음
    print(" * ", end="")

출력:

[2, 2, 2, 3]
{2: 3, 3: 1}
[2, 2, 2, 3, 3, 3, 7]
{2: 3, 3: 3, 7: 1}
[2, 2, 2, 2, 3, 3, 5, 5]
{2: 4, 3: 2, 5: 2}
{}
[2, 2, 2, 2, 3, 3, 5, 5]
3600 = 2^4 * 3^2 * 5^2