Ch1 최소공배수

최소공배수란?

최소공배수는 두개 이상의 숫자의 배수가 서로 같은 수 중에서 가장 작은 수를 의미한다.

예를 들면 2 와 3의 공배수는 6,12,18,24...이 있고 그중에서 6이 최소공배수이다.

Python을 이용한 최소공배수 나타내기

# 최소공배수 구해보기
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 = int(input()) #a라는 함수를 만들어 수를 저장한다
b = int(input()) #마찬가지로 b라는 함수를 만들어 수를 저장한다

a,b 함수에 숫자를 입력 받고 나면 짧은 코드를 입력하기 위해 반복문을 사용한다

for i in range(max(a,b),a*b+1): #반복문을 실행하는 코드

a와 b의 최소공배수를 구하기 위해 조건문을 이용하여 최소공배수만 값이 나오게 한다.

  if i%a==0 and i%b==0:
    print(i)
    break

만약에 a와 b가 같은 수를 곱해졌을때의 수가 같으면 a와b에 곱한수를 출력한다

Ch2 최대공약수

최대공약수란?

최대공약수는 두개 이상의 숫자의 공약수 중 가장 큰수를 의미한다

예를 들면 8과 12의 공약수는 1,2,4 이므로 최대공약수는 4이다

Python을 이용한 최대공약수 나타내기

#최대공약수만 구하기
a,b = map(int,input().split())

for i in range(min(a,b),0,-1):
  #a와 b 모두 나누어 떨어지면 공약수다
  if a%i==0 and b%i==0:
    print(i)
    break

코드에 대한 설명

숫자를 받는 코드를 처음으로 쓴다

a,b = map(int,input().split()) #a와 b의 수를 한번에 받을 수 있다

두번째로 반복문을 이용한다

for i in range(min(a,b),0,-1): #큰수부터 찾으면 최댓값이 나온다

마지막으로 최대공약수를 구할수 있는 조건문을 만든다

  #a와 b 모두 나누어 떨어지면 공약수다
  if a%i==0 and b%i==0:
    print(i)
    break

공약수를 구한 후 그 중에서 마지막에 나오는 수를 최대공약수로 정한다

Ch3 유클리드 호제법

유클리드 호제법이란 위에 이미지 같이 A와 B의 최대공약수가 B와 R의 최대공약수가 같을때를 말한다

예시:
1112 % 695 = 417
695 % 417 = 278
417 % 278 = 139
278 % 139 = 0
0이 될때까지 나누어진다

• 유클리드 호제법은 나눗셈만 반복해서 최대공약수(GCD)를 구할 수 있다.

• 두 개의 수가 아무리 커도 정해진 순서로 계산하면 효율적으로 최대공약수를 구할 수 있다.

유클리드 호제법을 이용한 코드

a = int(input())
b = int(input())

while b>0:
  a ,b = b, a%b
print(a)