최대공약수 찾는 과정

* 참고 : 약수 구하는 과정

- 약수는 짝을 이루고 있음(ex. 6 : 1,6 & 2,3)

- 따라서 자기자신을 제외한다면 약수는 n/2보다 클 수 없음

# n의 약수를 구하는 과정
divisor[]
for i in range(1,(n//2+1)):
	if n%i == 0:
    	divisor.append(i)
divisor.append(n)
print(divisor)

 

1. 공약수로 구성된 리스트에서 최댓값 찾기

# n, m의 최대공약수 찾는 과정
divisor=[]
for i in range(1, (n//2+1)):
	if (n%i==0) and (m%i==0):
    	divisor.append(i)  # 공약수를 넣음
result = max(divisor)  # 공약수 중 최댓값 : 최대공약수
print(result)

 

2. 유클리드 호제법

# n, m
while m != 0:
	n, m = m, n % m
print(a) # 최대공약수

[위키백과] 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다