(정수론/파이썬) 최대공약수(gcd) 구하기 (옛날식)

# 최대공약수(gcd)를 유클리드 호제법이 아닌, 구식으로 단순무식하게 구하는 방법
# gcd(a, b)가 주어졌을 경우, a의 약수를 모두 구하고, b의 약수를 모두 구한 다음, 
# a의 약수들과 b의 약수들의 교집합을 구해서 그중 가장 큰수를 출력한다.

# '친절한 수론 길라잡이' 33쪽

# 약수 구하는 함수
def getDivisor(num):
  divisors = []
  root_num = round(num ** 0.5)
  # sqrt(num)까지만 조사하면 된다. 단, round로 하면 소수점 이하는 버리기 때문에 
  # 아래 range에서 돌릴 때는 +1을 해줘야 한다.
  
  for i in range(1, root_num+1):
    if num % i == 0:  # 나눠지면
      divisors.append(i)  # 제수(나누는 수)가 약수가 되고
      divisors.append(num // i)  # 그 몫도 약수가 된다

  # 구한 것을 set 함수를 통해 중복을 제거하고 다시 리스트로 바꾼 다음, 정렬해서 리턴한다.
  return sorted(list(set(divisors))) 


# 최대공약수를 삽질로 구하는 함수
def my_gcd2(a, b):
  a_set = getDivisor(a)  # a의 약수를 모두 구한다
  b_set = getDivisor(b)  # b의 약수를 모두 구한다
  #print(a_set)
  #print(b_set)
  c_set = set(a_set) & set(b_set) # 두 약수들의 교집합을 구한다. 공약수들이 된다.
  
  return max(list(c_set))                    # 리스트로 바꾸어 최대값을 구한다.
  
  
print(my_gcd2(12, 20)) # 4
print(my_gcd2(18, 30))  # 6
print(my_gcd2(225, 120))  # 15
print(my_gcd2(12345, 67890))  # 15
print(my_gcd2(54321, 9876))  # 3
print(my_gcd2(1160718174, 316258250)) # 1078
print(my_gcd2(7919, 78498)) # 둘 다 소수임