최대공약수 (Greatest Common Divisor)
- 둘 이상의 공통 약수중 가장 튼수
- 어떤 수로 두 수를 나눴을 때 나눠지는 가장 큰 수
예제)
첫번째 수 = 6
두번째 수 = 4
첫번쨰 수의 약수 = 1,2,3,6
두번째 수의 약수 = 1,2,2,4
두수의 공약수 = 1,2
공약수중 가장 튼수 = 2
a = int(input())
b = int(input())
divisor = []
for i in range(1,min(a,b)+1):
if a%i ==0 and b%i==0:
divisor.append(i)
print(divisor[-1])이 코드는 a와 b를 입력받고 divisor(약수)라는 리스트를 만들어준다. 이 코드는 공약수중에서 가장 큰수를 프린트하게 설계되어있다.
하지만 리스트 없이 최대공약수만 구할수있는 코드도 있다.
a= int(input())
b= int(input())
for i in range(min(a,b),0,-1):
if a%i==0 and b%i==0:
print(i)
break가능한 모든 경우의 수를 다 확인해야 한다.
즉, 다음과 같이 주어진 a와 b정수 중 작은 정수부터 1까지 -1씩 감소하면서 for문을 돌리면 최대공약수를 찾을 수 있다.
최소공배수 (Least Common Multiple)
- 둘 이상의 수의 공통 배수중 가장 작은 것
- 두 수로 어떤 수를 나눴을 때 나눠지는 가장 작은 수
예제)
첫번째 수 = 6
두번째 수 = 4
첫번쨰 수의 배수 = 6,12,18,24,30 ...
두번째 수의 배수 = 4,8,12,16,20,24 ...
두수의 공배수 = 12,24 ...
공배수중 가장 작은수 = 12
a= int(input())
b= int(input())
for i in range(max(a,b),a*b+1):
if i%a==0 and i%b==0:
print(i)
break이 코드는 a와 b를 입력받고 이들의 최소공배수를 찾아준다. 이 코드는 a와 b중 큰수부터 a와 b를 곱한수까지를 경우의 수로 두고 for문을 돌려 가장 작은 공배수를 찾아준다.
유클리드 호제법을 이용한 최대공약수 찾기
- 두 수의 최대공약수를 구하는 획기적인 방법
- 원래는 두 수를 소인수분해하여 공통 약수를 찾는다
위 사진을 설명하자면 A와 B의 최대공약수와 B와R의 최대공약수가 같다
예제)
1112 % 695 = 417
695 % 417 = 278
417 % 278 = 139
278 % 139 = 0
1112를 695로 나누고 남은 나머지는 417
그 다음 695를 417로 나누고 남은 나머지는 278
그 다음 417를 278로 나누고 남은 나머지는 139
그리고 마지막으로 278을 139로 나누고 남은 나머지는 0
설명:
유클리드 호제법은 큰 수를 작은 수로 나누고, 그 나머지를 다시 제수로 나누는 반복적인 방법을 통해 최대공약수를 구하는 방법이다.
유클리드 호제법과 위에 있는 최대공약수를 구하는 방법중, 유클리드 호제법을 이용하여 최대공약수를 구하는 방법이 훨씬 간단하고, 효율적이다.
코드:
a= int(input())
b= int(input())
while b>0:
a,b = b,a%b
print(a)
끝!