데이터분석/셋째주

기초수학 : 최대공약수

핑크댕댕이 2023. 10. 19. 04:47
728x90

 

공약수

두 개 이상의 수에서 공통된 약수를 공약수라고 한다.

12의 약수 → 1, 2, 3, 4, 6, 12
20의 약수 → 1, 2, 4, 5, 10, 20
공약수 →   1  ,   2  ,   4   

 

 

 

최대공약수

공약수 중 가장 큰수를 최대공약수라고 한다.

12의 약수 → 1, 2, 3, 4, 6, 12
20의 약수 → 1, 2, 4, 5, 10, 20
●공약수 →   1  ,   2  ,   4   
●최대공약수 →   4   

 

 

소인수분해를 이용하면, 최대 공약수 및 공약수를 구할수 있다.

( 소인수분해 : 1보다 큰 정수를 소인수의 곱으로 나타낸 것 )

12의 소인수분해 : 2 × 6  → 2 × 2 × 3  → 
 2^2 × 3
20의 소인수분해 : 2 × 10  → 2 × 2 × 5  →  2^2 × 5
  ●최대 공약수 : 


  공통인 소인수의 거듭제곱에서 지수가 작은 수를 모두 곱한다.  

2^2  →    4   
  ●공약수 : 


  최대공약수의 약수 

  1  ,   2  ,   4    

 

14의 소인수분해 : 2 × 7
 2 × 7
20의 소인수분해 : 2 × 10  → 2 × 2 × 5  →  2^2 × 5
  ●최대 공약수 : 


  공통인 소인수의 거듭제곱에서 지수가 작은 수를 모두 곱한다.  

  2   
  ●공약수 : 


  최대공약수의 약수 

  1  ,   2  

 

36의 소인수분해 : 2 × 18  → 2 × 2 × 9 
→ 2 × 2 × 3 × 3  → 
2^2 × 3^2
60의 소인수분해 : 2 × 30  → 2 × 2 × 15  →
2 × 2 × 3 × 5  → 		 2^2 × 3 × 5
  ●최대 공약수 : 


  공통인 소인수의 거듭제곱에서 지수가 작은 수를 모두 곱한다.  

2^2 , 3  → 2^2 × 3  →    12    
  ●공약수 : 


  최대공약수의 약수 

  1  ,   2  ,   3  ,   4  ,   6  ,   12      

 

 

 

소수로 나눗셈을 하면, 좀 더 편리하게 최대공약수를 구할 수 있다.

두개 이상의 수를 소인수로 더이상 나누어지지 않을 때까지 나눈다.

12와 20의 최대공약수 36와 60의 최대공약수
  2   │  12  ,  20
       └───────
  2   │    6  ,  10
       └───────
  ↓          3  ,    5


   2   │  36  ,  60
       └───────
  2   │  18  ,  30
       └───────
  3   │    9  ,  15
       └───────
  ↓          3  ,    5
  2  ×  2   =   4
최대공약수 :   4     		  2  ×  2  ×  3   =   12
최대공약수 :   12    
공약수 (최대공약수의 약수)
  1  ,   2  ,   4   		 공약수 (최대공약수의 약수)
  1  ,   2  ,   3  ,   4  ,   6  ,   12      

 

 

 

[실습]

다음 수의 최대 공약수 및 공약수를 구해보자

  • 12, 54, 72 의 최대공약수 및 공약수
  • 25, 115, 255 의 최대공약수 및 공약수
12와 54, 72의 최대공약수 25와 115, 255의 최대공약수
  2   │  12  ,  54  ,  72
       └──────────
  3   │    6  ,  27  ,  36
       └──────────
  ↓          2  ,    9   ,  12		   5   │  25  ,  115  ,  255
       └──────────
  ↓          5  ,    23  ,    51
  2  ×  3   =   6
최대공약수 :   6    		   5
최대공약수 :   5    
공약수 (최대공약수의 약수)
  1  ,   2  ,   3  ,   6    		공약수 (최대공약수의 약수)
  1  ,   5  

 

 

[실습]

빵 112개와 우유 80개를 학생들한테 남김없이 동일하게 나누어 주려고 할때, 최대 몇 명의 학생이 빵과 우유를 받을 수 있는지 계산해보자.

그리고 학생 한 명이 받게 되는 빵과 우유의 개수를 계산해보자.

 

  • 112와 80의 최대공약수
  • 학생 한 명이 받게 되는 빵과 우유 개수
112와 80의 최대공약수
  2   │  112  ,  80
       └───────
  2   │   56  ,  40
       └───────
  2   │   28  ,  20
       └───────
  2   │   14  ,  10
       └───────
  ↓          7  ,    5
  2  ×  2   ×  2   ×  2   =   16
최대공약수 :   16    
학생 한 명이 받게 되는 빵과 우유
112 / 16 = 7
80 / 16 = 5
빵 7개, 우유 5개

 

 

 

유클리드 호제법을 이용해서 최대공약수를 구할 수 있다.

   x, y의 최대공약수는 y, r(x%y)의 최대공약수와 같다.   

 

x, y 의 최대공약수 = y, (x/y) 의 최대공약수

x   y   r  
12 % 36 = 12
  ↙   ↙   ↩
36 % 12 = 3  나머지가 0일 때까지 나눗셈한다. 
  ↙   ↙   ↩
12 % 3 = 0  
  ↓
최대공약수		  

 

 

 

파이썬 이용

for 문과 유클리드 호제법을 이용해서 최대 공약수를 구하자.

 

[실습] 두개의 수를 입력하면 공약수와 최대공약수를 출력하는 코드를 작성하자.

#전제조건: num2는 num1보다 큰 정수를 입력한다.

num1 = int(input('1보다 큰 정수 입력: '))
num2 = int(input('1보다 큰 정수 입력: '))
maxNum = 0

for i in range(1, (num1 + 1)):
	if num1 % i == 0 and num2 % i == 0:	#공약수
		print(f'공약수: {i}')
        maxNum = i

print(f'최대공약수: {maxNum}')

 

 

[실습] 세개의 수를 입력하면 공약수와 최대공약수를 출력하는 코드를 작성하자.

#전제조건: num2는 num1보다 큰 정수를 입력한다.

num1 = int(input('1보다 큰 정수 입력: '))
num2 = int(input('1보다 큰 정수 입력: '))
num3 = int(input('1보다 큰 정수 입력: '))
maxNum = 0

for i in range(1, (num1 + 1)):
	if num1 % i == 0 and num2 % i == 0 and num3 % i == 0:	#공약수
		print(f'공약수: {i}')
		maxNum = i

print(f'최대공약수: {maxNum}')

 

 

[실습] 유클리드 호제법을 이용해서 최대공약수를 구할 수 있다.

#전제조건: num2는 num1보다 큰 정수를 입력한다.

num1 = int(input('1보다 큰 정수 입력: '))
num2 = int(input('1보다 큰 정수 입력: '))

temp1 = num1; temp2 = num2

while temp2 > 0:
	temp = temp2
	temp2 = temp1 % temp2
	temp1 = temp

print(f'{num1}, {num2}의 최대공약수: {temp1}')

for n in range(1, (temp1 + 1):
	if temp1 % n == 0:
		print(f'{num1}, {num2}의 공약수: {n}')

 

 

 

 

 

반응형