[파이썬 개념정리] 유클리드 호제법, 최대공약수 구하기

     유클리드 호제법이란?
: 2개의 자연수 최대공약수를 구하는 방법 중 하나.

* 원리

step1. 큰 수를 작은수로 나누기.
step2. 작은수 -> 큰 수, 나머지 -> 작은 수

step3. 나머지가 0이 될 때 까지 큰 수를 작은수로 나누기

step4. 나머지가 0이 될 때의 작은수 -> 최대공약수

* 예시로 이해하기

48과 26의 약수를 구해보자.

step1. 큰 수를 작은수로 나누기.
     48 / 26 = 1 ... 22

step2. 작은수 -> 큰 수, 나머지 -> 작은 수

     큰 수 = 26, 작은 수 = 22

step3. 나머지가 0이 될 때 까지 큰 수를 작은수로 나누기

    -> 26 / 22 = 1 ... 4
         => 22, 4

     -> 22 / 4 = 5 ... 2

         => 4, 2

      -> 4 / 2 = 2 ... 0

step4. 나머지가 0이 될 때의 작은수 -> 최대공약수

     최대공약수 : 2

 

* 파이썬으로 구현하기 위해 필요한 파이썬의 문법적 요소

1. 반복 구조 : 동일한 명령이 반복되면서 실행되는 구조 - for문

#for i in range(시작할 숫자, 종료할 숫자, 증가량)
for i in range(1, 10, 1)		#1, 2, 3, 4, ..., 9
for i in range(1, 100, 3)		#1, 4, 7, ... , 97
for i in range (10, 1, -1)		#10, 9, ..., 2

 

1-2) 반복 구조 : 횟수 제한 없이 무제한 반복 실행하는 구조 - while 문

#while (조건식) : <실행문장>
#조건식이 참일 때 실행문장 반복

while True : <실행문장>		#무한반복, break로 중지 가능.

 

2. 선택 구조 : 둘 중 하나의 명령을 선택하여 실행하는 구조

#if (조건식) : <실행문장>
#조건식이 참일 때 실행문장 실행

n=1
if (n==1) : 
	print("참")

 

3. 기타 명령어

#input : 사용자에게 문자열을 입력할 수 있는 명령어
#int : 문자열을 정수로 변환
# = : 변수에 저장
# == : 같다의 의미
# % : 나눗셈의 나머지

#사용예시
n=int(input())

 

* 유클리드 호제법 코드 파이썬으로 구현하기

s=int(input('작은수 : '))
b=int(input('큰수 : '))


while True : 
    r=b%s
    if r==0 : 
        print('최대공약수', s)
        break
    b=s
    s=r

#출력결과
작은수 : 26
큰수 : 48
최대공약수 2

 

사실상, 꼭 큰 수와 작은 수를 순서대로 받을 필요는 없다.

왜냐하면 설사 큰 수와 작은 수가 반대로 들어온다고 해도 step1을 한 번 거치면 다시 재정렬되기 때문이다.

 

#gcd = Greatest Common Divisor

def gcd(b, s) : 
	while(b%s!=0) : 
    	temp = s
        s=b%s
        b=temp
	return s