Python - 최대 공약수 / 약분 - 알고리즘, 구현 코드

 

최대 공약수 (GCD, Great Common Divisor)

두 수의 최대 공약수 알고리즘

조건 1. 두 수 x와 y에서 x는 y보다 커야한다.

x > y

 

조건 2. y가 0일 경우, x를 출력하고 알고리즘을 종료한다.

if y == 0 :
	print(x)

 

조건 3. x 와 y를 나눈 나머지의 값이 0이면 y를 출력하고 알고리즘을 종료한다.

if x % y == 0 :
	print(y)

 

조건 4. x와 y를 나눈 나머지 값이 0이 아니면 x에 y의 값을, y에 나머지 값으로 대입하여 조건3를 다시 수행한다.

while x % y != 0 :
    temp = x % y
    x = y
    y = temp

---

최대 공약수 구하기 코드

• 함수에 두 수의 값을 입력하면 최대공약수의 값 반환

def findGcd(xNumerator, xDenominator) :
  # 분모(xDenom), 분자(xNum), 임시 저장 변수(tempValue)
  tempValue = 0
  xNum = xNumerator
  xDenom = xDenominator

  # 최대 공약수 구하기
  while (xDenom) :
    tempValue = xNum % xDenom
    xNum = xDenom
    xDenom = tempValue
  return xNum

---

결과

15와 25의 최대 공약수는 5이다.

findGcd(15, 25)
>>> 5

---

약분 (Reduction)

약분 알고리즘

조건 1. 두 수의 최대 공약수를 구한다.

위에서 설명하였으므로 생략

 

조건2. 최대 공약수에 각각의 두 수를 나눈다

# 위의 결과에서 최대 공약수가 5라는 전제하에서 진행
# gcd = 5

# 입력 값 분자 15, 분모 25
# xNumerator = 15, xDenominator = 25

print(int(xNumerator/gcd), "/", int(xDenominator/gcd))

---

약분 코드

• 최대 공약수를 각각의 두 수에 나눈 값 반환

def findReduction(xNumerator, xDenominator) :
  # 분모, 분자, 임시 저장 변수
  tempValue = 0
  xNum = xNumerator
  xDenom = xDenominator

  # 최대 공약수 구하기
  while (xDenom) :
    tempValue = xNum % xDenom
    xNum = xDenom
    xDenom = tempValue
  # 최대 공약수 저장 변수(gcd)
  gcd = xNum

  # 약분
  return int(xNumerator/gcd), int(xDenominator/gcd)

---

결과

• 15/25의 약분 결과는 3/5이다.

# 분자 15, 분모 25 값 설정
iNumerator = 15
iDenominator = 25

# 약분된 값 각 변수에 저장
redValNum , redValDenom = findReduction(iNumerator, iDenominator)

print(reducValNum , "/", reducValDen)
>>> 3 / 5

---

참고

• 위키백과 - 유클리드 호제법

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95#%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

유클리드 호제법 - 위키백과, 우리 모두의 백과사전