python을 이용한 최대공약수 알고리즘

Python을 이용하여 최대공약수를 구해보도록 하겠습니다.
먼저 직관적으로 짤수있는 코딩방법과 알고리즘을 이용하여 코딩을 해보겠습니다.

만약 구해야 할수 15 와 3의 최대공약수라면 두수의 최대공약수는 3입니다.
프로그래밍을 할때는 1부터 3까지의수를 각각 15와 3에 나누엇을때 나머지가 둘다 0이 되는 수 중에서
가장 큰수가 최대공약수가 되는 것을 확인할수 있습니다.

 여기서 range라는 함수는 range(5)를 하였을경우 0 1 2 3 4 를 출력합니다 그래서 1부터 b까지 출력하기위해서 range(1,b+1) 를 해주었습니다.
위의 프로그램을 살펴보면 필요없는 과정도 포함되어 있다는 것입니다. 이젠 수학적인 알고리즘을 이용해서 코딩해 보겠습니다. 최대공약수 알고리즘으로 가장 잘알려진 알고리즘은

유클리드 알고리즘

예를 들어보겠습니다.
25 와 15 의 최대공약수 %<- 나머지를 구하는 부호라하면
25%15 =10
15%10 = 5
10%5 = 0
만약 나머지가 0이 나오는 순서의 나눈값이 최대공약수가 되는것을 확인할수 있습니다.

이것을 python으로 짤려면 생각해야 할것은 
첫번째 최대공약수를 구할 두수를 저장할 변수 a와 b
a와b의 나머지를 저장할 c
만약 c값이 0일경우는 b가 최대공약수
아닐경우는
a에 b를 저장  b에 c를 저장하고 위의 과정을 반복하면 됩니다 c값이 0이 나올때까지
머릿속에 한번 어떻게 짤지 한번 생각합니다

언뜻보면 알고리즘을 이용한것보다 단순하게 직관적으로 짠게 더 간단해 보일수 있습니다.
하지만 반복문이 몇번실행되는지를 살펴보면
15 10 의 최대공약수를 구하는 과정이서
위의 코딩은 10번의 박복문을 반복하고
유클리드알고리즘은
3번정도의 반복으로 값을 구할수있습니다.
이처럼 알고리즘이 좋을수록 짧은시간안에 원하고자하는 수를 구할수있습니다.