[C언어] 최대공약수, 최소공배수

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

#include <stdio.h>   void f( int num1, int num2 ){       int num3 = 1;     while(num3 != 0 ){           num3 = num1 % num2;         num1 = num2;         num2 = num3;     }     printf("유클리드 호제법 최대공약수는 %d입니다.\n", num1 );   } int main() {     int n1, n2;     fputs("최대공약수 인자 설정 : ", stdout);     scanf("%d %d", &n1, &n2 );       int i, max;     for(i = 1; i <= n1; i++)     {         if( n1 % i == 0 && n2 % i == 0 ){             max = i;         }     }     printf("%d와 %d의 최대 공약수는 %d입니다.\n", n1, n2, max);       f(n1, n2);           ////////////////////////////////////다른방법     int ucNum;     ucNum = n1;     if( n1 > n2)         ucNum = n2;       for(; 0<ucNum; --ucNum){         if( n1 % ucNum == 0 && n2 % ucNum == 0 ){               printf("최대공약수: %d, 최소공배수 : %d \n", ucNum, n1*n2/ucNum );             break;         }     }       return 0; }

 

 

 

약수란? 

1은 모든 수의 약수이고, 어떤 수는 자기 자신의 약수이다. 또한 어떤 정수도 0으로 나눌 수 없다. 따라서 0은 어떤 수의 약수도 아니다.

 

 

 

1) 공약수 : 두 개 이상의 자연수의 약수 중에서 공통인 것

--------------------------------------------------------------------------------------------------------

1. 최대공약수

(1) 공약수 : 두 개 이상의 자연수의 약수 중에서 공통인 것

최대공약수

(2) 최대공약수 : 공약수 중에서 가장 큰 수
(3) 최대공약수의 성질 : 두 개 이상의 자연수의 공약수는 그들의 최대공약수의 약수이다.
(4) 서로소 : 공약수가 1뿐인 두 자연수

2. 최대공약수 구하는 법

(1) 나눗셈을 이용한 방법
① 공통인 소인수로 각 수를 나눈다.
② 몫이 서로소가 될 때까지 계속 나눈다.
③ 공통으로 나온 소인수를 모두 곱한다.

------------------------------------------------------------------------------------------------------------------

  

1. 최소공배수

(1) 공배수 : 두 개 이상의 자연수의 공통인 배수

최소공배수

(2) 최소공배수 : 공배수 중 가장 작은 수

(3) 최소공배수의 성질 : 두 개 이상의 자연수의 공배수는 그들의 최소공배수의 배수이다.

2. 최소공배수 구하는 방법

(1) 나눗셈을 이용한 방법
① 두 수 이상의 공통인 소인수로 각 수를 나눈다.
② 나누어 떨어지지 않는 수는 그대로 내린다.
③ 몫이 서로소가 될 때까지 계속 나눈다.
④ 공통으로 나온 소인수에 마지막 몫을 모두 곱한다.

 

최소공배수는 두수의 곱에 최대공약수로 나눠주면 됩니다.

 

 

 

이걸 왜하냐?

 

최소공배수 -> 3일마다 오는 기차와 7일마다 오는 배가 있다. 오늘 기차와 배가 왔다면 몇일 후에 기차와 배가 동시에 올까? ( 21일 )

 

1 |3, 7

    ----

    3  7

최대공약수 1, 최소공배수 3*7 /1 = 21일

 

--------------------------------------------------------------------------------------------------------------------------

최대공약수 -> 과자 20봉지와 음료수 12캔이 있다. 이걸 공평하게 나눠주려 하면 최대 몇명에게 나눠줄 수 있을까? (하나의 과자나 음료수를 나눠서는 안된다.)