Python 라이브러리 없이 기약분수 구하는 방법

이번 시간에는 Python 라이브러리를 사용하지 않고 기약분수를 구하는 방법에 대해서 알아보겠습니다.

10/8 의 분수가 있다고 가정합니다.

분자는 10, 분모는 8 이라 해당 분수는 기약 분수가 아닙니다.

기약분수로 나타내려면 분자와 분모의 최대공약수를 분자와 분모에 나눠줘서 표현해 줘야 합니다.

최대공약수를 구하기 위해서는 유클리드 호제법을 사용합니다.

예를 들어 분자를 분모로 나눈 나머지 값이 0이면 해당 분모는 최대공약수가 됩니다. 

만약 나머지 값이 0이 아니면 분모를 나머지 값으로 다시 나눠줍니다. 이렇게 반복해서 나머지 값이 0이 나올 때의 나눈 값이 최대 공약수가 됩니다. 만약 나머지 값이 이전의 나머지 값과 같다면 최대공약수가 존재하지 않습니다.

10을 8로 나누면 2가 남습니다. 0이 아니기 때문에 8은 최대공약수가 아닙니다.

다시 8을 2로 나눠주면 나머지가 0이 됩니다. 이때 2는 최대공약수가 됩니다.

최대공약수 2를 구했으니, 분자 10을 2로 나눠주고 분모 8을 2로 나눠주면 5/4 의 기약분수 형태가 됩니다.

분자	분모	나머지
10	8	2
8	2 (최대공약수)	0

이것을 코드로 짜보면 다음과 같습니다.

answer = []
numer1 = 10
denom1 = 8

numer2 = numer1
denom2 = denom1

gcf = 1
pretemp = 1
temp = 1

while temp != 0:
	temp = numer2 % denom2
    if temp == 0:
    	gcf = denom2
        break
    if pretemp == temp:
    	gcf = 1
        break
    numer2 = denom2
    denom2 = temp
    pretem = temp
    
if gcf != 1:
    numer1 = int(numer1/gcf)
    denom1 = int(denom1/gcf)
    answer.append(numer1)
    answer.append(denom1)
else:
    answer.append(numer1)
    answer.append(denom1)

 

이렇게 Python 라이브러리를 사용하지 않고 기약분수를 구하는 방법에 대해서 알아봤습니다.

유용하셨다면, 공감과 구독 부탁 드립니다.

감사합니다. :)