유클리드 알고리즘으로 최대공약수를 구해보자

원래썻던 방법

a,b=map(int,input().split())
ans=[]
# 최대공약수가 될수있는 숫자전부를 검사해서 최대공약수를 찾아낸다
for i in range(min([a,b]),0,-1): 
    if a%i==0 and b%i==0:
        최대공약수=i
        break
print(최대공약수)

이번에 배운 유클리드 알고리즘 이용해서 최대공약수구하는 코딩을 해보았다

def gcb(a,b):
    b=min([a,b])
    a=max([a,b])
    if b==0:
        return a
    return gcb(b, a%b)

a,b=map(int,input().split())
gcb(a,b)

시간체크 유클리드 알고리즘은 몇초가걸릴까? 

in

import timeit
 
start_time = timeit.default_timer() # 시작 시간 체크
 
def gcb(a,b):
    b=min([a,b])
    a=max([a,b])
    if b==0:
        return a
    return gcb(b, a%b)

print(gcb(254541,21845))
    
terminate_time = timeit.default_timer() # 종료 시간 체크  
 
print(f"{terminate_time - start_time}초 걸렸습니다.")

out

17
0.002226368000265211초 걸렸습니다.

원래썻던 방법

 

in

import timeit
 
start_time = timeit.default_timer() # 시작 시간 체크
 

a=254541
b=21845
for i in range(min([a,b]),0,-1):
    if a%i==0 and b%i==0:
        최대공약수=i
        break
print(최대공약수)
    
terminate_time = timeit.default_timer() # 종료 시간 체크  
 
print(f"{terminate_time - start_time}초 걸렸습니다.")

 

out

17
0.0048425109998788685초 걸렸습니다.

약 두배정도 빨라진것을 확인하였다

 

결론: 최대공약수 구할때는 유클리드 알고리즘