5 최대 약수 구하기

1. 두 수 중 더 작은 값을 i 에 저장
2. i 가 두 수의 공통된 약수인지 확인
3. 공통된 약수이면 이 값을 결과값
4. 공통된 약수가 아니면 i를 1만큼 감소 반복

def gcd(num1,num2):
     
    num=max(num1,num2)
    gcd=0
    for i in range (2,num+1):
        if(num1 %i ==0 and num2 % i ==0) :
            gcd = i
    return gcd
    
print(gcd(15,12))

답안

def gcd(num1,num2):
     
    gcd=min(num1,num2)
    while True:
        if num1%gcd==0 and num2 %gcd ==0:
            return gcd 
        gcd=gcd-1
    
print(gcd(22,11))

유클리드 알고리즘

• a와 b의 최대 공약수는 b와 a를 나눈 나머지의 최대 공약수와 같다.

60, 24

gcd(60,24) ==gcd(24,12) == gcd(12,0) == 12

def euclid(num1,num2) :
    large= max(num1,num2)
    small =min(num1,num2) 
    if(small) ==0 :
        return large
    return euclid(small,large%small) # 작은 값으로 자기 자신을 호출 

print(euclid(33,22))