약수, 배수와 소수 2

 

 

 

 

[유클리드 호제법]

두 개의 자연수 N, M(단 N>M)에서 N을 M으로 나눈 나머지를 r이라고 했을 때 GCD(N,M) = GCD(M,r) 이고 r이 0이면 그 때 M이 최대공약수이다.

 

# 최소공배수 : A와 B의 최대공약수를 먼저 구하고 A와 B의 곱을 최대공약수로 나눈다.

T = int(input())

for i in range(T):
  A, B = map(int, input().split())
  aa, bb = A, B
  # 결과적으로 B에 최대공약수가 들어감
  while a%b !=0:
    a,b = b,a%b
  print(aa*bb//b)

 

 

<1934번 : 최소공배수>

T = int(input())

for i in range(T):
    A,B = map(int, input().split())
    aa, bb = A,B
    # 결과적으로 B에 최대공약수가 들어감
    while A%B!=0:
        A,B = B, A%B
    print(aa*bb//B)

 

☆ 이 문제에선 유클리드 호제법으로 최대공약수를 구한 뒤 최소공배수를 구하자.

 

[최대 공약수를 구하는 방법]

1. 반복문

def gcd(a,b):
    if a>b:
        a,b = b,a
    
    for i in range(a, 0, -1):
        if a%i == 0 and b%i ==0:
            break
    return i

 

2. math라이브러리의 gcd함수

import math
a, b = map(int, input().split())

gcd = math.gcd(a,b)

 

3. 유클리드 알고리즘

a,b = map(int,input().split())
aa, bb = a, b
while a%b != 0:
a,b = b, a%b

 

 

 

<13241번 : 최소공배수>

A,B = map(int, input().split())
res = A*B

# 최대공약수(유클리드 호제법)
while B:
    if A>B:
        A,B=B,A
    B %= A

# 최소공배수
print(res//A)

 

→ 유클리드 호제법을 이용하여 최대공약수를 구하고, 이렇게 구한 최대공약수를 이용하여 최소공배수를 구한다.

 

 

<1735번 : 분수합>

A,B = map(int,input().split())
C,D = map(int,input().split())

numerator = (B*C+A*D) # 분자
denominator = B*D # 분모

# 최대공약수
def gcd(x,y):
    while y:
        x,y = y, x%y
    return x
gcd = gcd(numerator, denominator)

numerator = int(numerator/gcd) # 약분 : 최종 분자는 최대공약수로 나누기
denominator = int(denominator/gcd) # 약분 : 최종 분모는 최대공약수로 나누기

print(f"{numerator} {denominator}")

 

→ 기약분수 : 분모와 분자를 최대공약수로 나눈 것

→ 처음에 분수 더하는 걸 너무 어렵게 생각했음! '분자3 = 분자1 분모2 + 분자2 * 분모1' ← 이렇게 생각!!