(정수론/파이썬) 완전수, 부족수, 초과수 세기

# 연습문제 15.7.b
# sigma(n) = 2n을 만족하는 n을 완전수라 한다.
# sigma(n) > 2n 이라면 초과수, sigma(n) < 2n 이라면 부족수라 하자.
# 2와 100사이에 얼마나 많은 완전수, 부족수, 초과수가 존재하는지 세어보라.
# 100과 200사이에서도 초과수와 부족수를 찾아보아라.


# 소수 판정 함수. 소수면 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 factorize2(value):
  num = value  # 원래값을 보존한다.
  divisor_primes = [] # 분해된 인수를 차곡차곡 저장하는 리스트
  factorize_dict = {} # 리스트의 원소 갯수를 세어 넣는 용도
  
  root_val = int(num ** 0.5)+1
  i = 2
  found = False
  while True:
      # 소수 검증 때처럼 num까지 모두 나누어볼 필요는 없고 제곱근값 까지만 나누어보면 된다.
      if i >= root_val: break
    
      # i가 소수인지 검사해서 소수라면 num을 i로 나눈다
      # i로 나눠서 나머지가 0이라면, 인수분해가 한번 된 것이다.
      if isPrime(i) and num % i == 0:
          divisor_primes.append(i) # 나누는 수를 저장
          num = num // i   # 몫, 가령 24//2 = 12
          root_val = int(num ** 0.5)+1
          if found == False:
            found = True  # 찾았다는 표시를 함
          # 12는 소수가 아니므로 반복문 계속. 소수가 나오면 그 소수를 저장하고 반복문 종료.
          if isPrime(num):
              divisor_primes.append(num)
              break  # return divisor_primes
      else:
          i += 1 # 인수분해가 되지 않으면 젯수(나누는 수)를 1증가
  
  for n in divisor_primes:
      if n in factorize_dict:
          factorize_dict[n] += 1   
      else:  
          factorize_dict[n] = 1      
  
  if found == False:  # 소인수를 못 찾았다면 소수이므로
      factorize_dict[value] = 1
  
  return factorize_dict
  
  
  # 약수 구하는 함수: 향상된 버전
# 소인수분해 결과를 가지고 약수를 만듦
# 숫자가 클 경우, 속도 면에서 단순한 방식(버전1)보다 훨씬 빠름
# 50234902430546664의 약수를 구했을 때 버전2가 1초 걸리고, 버전1이 35초 걸림.
def getDivisor2(num):
  divisors = []
  res = factorize2(num) # 예) {2:3, 3:2, 7:1} 형태
  
  for key, value in res.items():
    divisor = []
    for i in range(value+1):
      divisor.append(key**i)
    divisors.append(divisor)
  # divisors : [[2**0, 2**1, 2**2, 2**3], [3**0, 3**1, 3**2], [7**0, 7**1]]
  # divisors : [[1, 2, 4, 8], [1, 3, 9], [1, 7]]
  
  while True:
    tmp = [] # 리스트 2개 원소를 서로 곱해서 약수를 만들어 임시 저장

    # 리스트를 하나씩 줄여나가는데 리스트가 하나만 남았으면 그것이 약수 집합이므로 종료한다
    if len(divisors) < 2:
      break
    # 리스트 2개의 각 원소를 서로 곱해서 약수를 만들어 저장
    for n in divisors[0]:  
      for m in divisors[1]:
        tmp.append(n * m)
        
    # divisors 안의 리스트는 예에서 3개이고, 리스트[0]과 [1]을 곱해서 약수를 만들고(tmp),
    # 기존 리스트[0]과 리스트 [1]을 삭제하고 1차 약수 리스트인 tmp를 리스트[0] 자리에 끼워넣는다.
    # 한번 실행을 거치면 이제 리스트 목록은 총 2개가 되었다.
    del divisors[0] # 원래 divisors[0] 삭제
    del divisors[0] # 원래 divisors[1] 삭제
    divisors.insert(0, tmp) # 생성된 tmp를 divisors 제일 앞에 끼워넣기
    
  return sorted(divisors[0]) # 리스트의 리스트이므로 바깥 대괄호를 제거하고 정렬해서 반환


# 시그마 함수: 자신을 포함한 모든 약수의 총합을 돌려주는 함수
# 예) 12의 시그마 함수값: 1, 2, 3, 4, 6, 12 을 모두 더한 값
# '친절한 수론 길라잡이' 105~106에서 소개
def sigma_fun(num):
  divisors = getDivisor2(num) #   # 소인수분해 방식으로 약수를 모두 구한다
  total = 0   # 합 초기화
  for d in divisors: # 약수들을 모두 합한다
    total += d
  return total


over_count = 0   # 초과수 개수
under_count = 0 # 부족수 개수
perfect_count = 0  # 완전수 개수

for n in range(2, 101):  # 2~100
  res = sigma_fun(n)
  if res < 2*n:  # 부족수
    under_count += 1
  elif res > 2*n: # 초과수
    over_count += 1
  else:
    perfect_count += 1
                                      # 2~100   # (101~200) # (201~300)
print(f"완전수 개수: {perfect_count}")  # 2      # 0         # 0  
print(f"초과수 개수: {over_count}")     # 22     # 24        # 23
print(f"부족수 개수: {under_count}")    # 75     # 76        # 77